二进制下的负数

看上去越基础的题，背后越有大道理。

背景

日常刷Leetcode题遇到一个很基础的题目。

原题链接

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

进阶：你能够不使用循环/递归解决此问题吗？

思路

正常想法就是一直mod 2和除以2判断是否是2的幂次方。

但看到这个进阶，Easy题必要达到好吗。

题目跟2的幂次方有关，计算机又是以2进制存储数据的。

这可能跟位操作有关，怎么一步到位呢？

分析一下2的幂次方的二进制。

1
2
3

DEC(2) = BIN(10)
DEC(4) = BIN(100)
DEC(8) = BIN(1000)

可以发现2的次幂二进制都是只有最高位是1，其他全是0的特征。

有什么办法通过位操作来直接检测这样特征的数呢？

介绍一下补码。

补码

一般计算机使用补码来存储负整数。

我们都知道int的数据范围是[-2,147,483,647, 2,147,483,647]

正好是-2^31-1和231-1。

为什么要减一呢？

因为二进制的最高位要存储符号。

如图，最高位0表示正数。

负数的最高位就是1。

既然能表达负数，那么减法可以转变为加上负数。

a - b = a + (-b)

如何保证直接转换为的负数与正数相加和正常相减一个效果呢？

直接把最高位换成1肯定是不行的。

至少要满足一个正数加自己的负数等于0吧。

这时补码就出现了。

求负整数的补码，将其原码除符号位外的所有位取反（0变1，1变0，符号位为1不变）后加1

这样做有什么效果，我们来看看。

1
2
3
4
5
6

 DEX(7) = BIN(0111)
//7的二进制符号位变成1 -> 1111
//除符号位取反 -> 1000
//加一 -> 1001
 DEX(-7) = BIN(1001)  
 DEX(7) + DEX(-7) = BIN(0111) + BIN(1001) = 0

补码神奇吧！

这样就可以将任意的减法操作转换为加法了。

那么这个补码对这道题来说有什么作用呢？

思路

一个正整数&(位与)自己的负数，得到最低位的1

例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

例一：
DEX(12)  = BIN(01100)
DEX(-12) = BIN(10100)
DEX(12) & DEX(-12) = BIN(01100) & BIN(10100) = BIN(00100)
//12最低位的1在从左往右数第三个位置，所以操作后结果是100

例二：
DEX(56)  = BIN(0111000)
DEX(-56) = BIN(1001000)
DEX(56) & DEX(-56) = BIN(0111000) & BIN(1001000) = BIN(0001000)
//56最低位的1在从左往右数第四个位置，所以操作后结果是1000

例三：
DEX(8)  = BIN(01000)
DEX(-8) = BIN(11000)
DEX(8) & DEX(-8) = BIN(01000) & BIN(11000) = BIN(01000) = DEX(8)

根据前面的分析，我们知道2的次幂二进制都是10，100，1000这样子的。

所以我们直接把它跟自己负数进行与操作，如果结果还是原来的数就说明这是2的次幂。(见例三)

代码

1
2
3

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (-n)) == n;
  }