一,计算某个正数的二进制表示法中 1 的个数
1 //求解正数的二进制表示法中的 1 的位数 2 private static int countBit(int num){ 3 int count = 0; 4 for(; num > 0; count++) 5 { 6 num &= (num - 1); 7 } 8 return count; 9 }
算法思路:每次for循环,都将num的二进制中最右边的 1 清除。
为什么n &= (n – 1)能清除最右边的1呢?因为从二进制的角度讲,n相当于在n - 1的最低位加上1。举个例子,8(1000)= 7(0111)+ 1(0001),所以8 & 7 = (1000)&(0111)= 0(0000),清除了8最右边的1(其实就是最高位的1,因为8的二进制中只有一个1)。再比如7(0111)= 6(0110)+ 1(0001),所以7 & 6 = (0111)&(0110)= 6(0110),清除了7的二进制表示中最右边的1(也就是最低位的1)。
二,获取某个数的第 i 位(判断某个数的第 i 位是0 还是 1?)
思路:如果第 i 位 与 1 相与 结果为1 表明第 i 位为1;如果为0 表明第 i 位为0
//获取 整数 num 的第 i 位的值 private static boolean getBit(int num, int i) { return ((num & (1 << i)) != 0);//true 表示第i位为1,否则为0 }
1 左移 i 位后,得到一个数,这个数只有第 i 位为1,其它位都为0
num 与这个数相与,得到的结果 要么是0,要么非0。结果为 非0 表示第 i 位为1,结果为0 表示第 i 位为0
三,将第 i 位设置为1
思路:第 i 位与0 或,值不变。第 i 位与1 或,变成1。因此,我们的目标是 num 与 一个第 i 位值为1,其它位的值都为0的数相 或
//将 整数 num 的第 i 位的值 置为 1 private static int getBit(int num, int i) { return (num | (1 << i)); }
四,将第 i 位设置为0(清0)
思路:第 i 位和0与,第 i 位就变成了0。其它位 都与 1 与,其它位保持不变。这样,就只把第 i 位清0了
//将 整数 num 的第 i 位的值 置为 1 private static int getBit(int num, int i) { int mask = ~(1 << i);//000100 return (num & (mask));//111011 }
总之,获取第 i 位的值,或者是将第 i 位置0或者置1 ,其总体思路就是:将 1 左移 i 位,然后再进行 与操作 或者 或操作。