位操作

常用操作

大家都知道>是比较两个对象的大小，那>>和>>>的区别呢？
>>和>>>都是移位操作；对正数的移位操作它们的功能都是一样的，如下：

其实就是将15除于4，得到的商。转换为二进制可能更直观（为了方便，下面的二进制操作我们都是以八位进行的，而不是32位）：

对正数的操作它们的效果都是一样的，那么对于负数的移位是否也是一样呢？看下面例子就知道了：

怎么会是这样的？负数的移位操作怎么变成正数了？同样我们将上面的式子转换为二进制来看看。首先我们得知道，在计算机中，负数是以补码的形式存储的（补码不知道？那你自己去好好学习点基础知识吧！）-15的补码是11110001，所以上面的操作转换为二进制如下所示：

　　根据上面的结果，我们可以清楚的看出：

1、当移位的数是正数的时候，>> 和>>>效果都是一样的；
2、当移位的数是负数的时候，>>将二进制高位用1补上，而>>>将二进制高位用0补上，这就导致了>>>将负数的移位操作结果变成了正数（因为高位用0补上了）。

https://discuss.leetcode.com/topic/50315/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently/2

https://discuss.leetcode.com/topic/49771/java-simple-easy-understand-solution-with-explanation

//Create Mask 
/* 创建掩码，用来清除n中i到j的位 
/* 示例：i = 2, j = 4。掩码为11100011。
int allOnes = ~0; // 等同于一连串的1

// 在位置j之前的位均为1，其余为0，left = 11100000 
int left = allOnes << (j + 1);

// 在位置i之后的位均为1，right = 00000011 
int right = ((1 << i) - 1);

// 除i到j的位为0，其余位均为1。mask = 11100011 
int mask = left | right;

/* 清除位置j到i的位，然后将m放进去 */ 
int n_cleared = n & mask; // 清除j到i的位


清零
a = 1 << p; // 除位p为1外，其余位均为0 
b = a - 1; // 前面全为0，后面跟p个1 
mask = ~b; // 前面全为1，后面跟p个0 
n = n & mask; // 将右边p个位清零

//添加1
a = 1 << (c1 - 1); // 位c1 - 1为1，其余位均为0 
b = a - 1; // 位0到位c1 - 1的位为1，其余位均为0 
n = n | b; // 在位0到位c1 - 1处插入1

int a = ~0; // 所有位置1
int b = a << (p + 1); // 位p左方的所有位为1，后跟p+1个0
n &= b; // 将位0到位p清零

n & (n - 1) drops the lowest set bit. It’s a neat little bit trick.

5.3 给定一个正整数，找出与其二进制表示中 1 的个数相同、且大小最接近的那两个数 （一个略大，一个略小）。（第 56 页）

1. 蛮力法 简单的做法就是直接使用蛮力：在n的二进制表示中，数出1的个数，然后增加或减小，直至 找到1的个数相同的数字。简单吧，但也没什么意思。还有没有更优的做法呢？当然有！

2. 位操作法：取得后一个较大的数

你会发现：给定一个数n和两个位的位置i和j，假设将位i从1翻转为0，位j从0翻转成1。若i > j，n就会减小；若i < j，则n就会变大。

5.4 解释代码((n & (n-1)) == 0)的具体含义。（第 56 页）

((n & (n-1)) == 0)检查n是否为2的某次方（或者检查n是否为0）

5.5 编写一个函数，确定需要改变几个位，才能将整数A转成整数B。（第 57 页）

for (int c = a ^ b; c != 0; c = c >> 1) {
 count += c & 1; 
 }


for (int c = a ^ b; c != 0; c = c & (c-1)) 
{ count++; 
}

上面的代码已经很不错了，不过还可以做得更好。上面的做法是不断对c执行移位操作，然 后检查最低有效位，但其实可以不断翻转最低有效位，计算要多少次c才会变成0。操作c = c & (c - 1)会清除c的最低有效位。(Same as 5.4)

5.7 数组A包含 0 到n的所有整数，但其中缺了一个。在这个问题中，只用一次操作无法取 得数组A里某个整数的完整内容。此外，数组A的元素皆以二进制表示，唯一可用的访问操作是 “从A[i]取出第j位数据”，该操作的时间复杂度为常数。请编写代码找出那个缺失的整数。你有 办法在O(n)时间内完成吗？（第 57 页）

你可能听到过非常类似的问题：给定一列0到n的数，其中只缺一个数字，把这个数找出来。 这个问题解决起来很简单，直接将这列数相加，然后与0到n的总和（即n * (n + 1) / 2）进行比较。 两者差值就是那个缺失的整数。 至于这一题，我们可以根据每个整数的二进制表示，求出它的值，然后计算总和。

这种解法的执行时间为n * length(n)，其中length为n中有多少个位。注意，length(n) = log 2 (n)， 因此，真正的执行时间为O(n log(n))，效率不够高！那么，我们该怎么办呢

-好好看答案！！