Bit Manipulation

Summary of Basic Bit Manipulation

Count 1 in Binary

数的二进制表示中有多少位1. 有两种方法。

  1. 每次把各位的数和 1 做 & 运算,然后计数,右移进行下一位。
class Solution {
public:
    /**
     * @param num: an integer
     * @return: an integer, the number of ones in num
     */
    int countOnes(int num) {
        // write your code here
        int counter = 0;
        for (int i = 0; i < sizeof(int)*8; i++) {
            counter += num & 1;
            num >>= 1;
        }
        return counter;
    }
};
  1. 把 num 和 num - 1 做 & 运算, 直到num为0,有多少次运算就有多少个1. 因为每次“&”都会去掉num最右边的1.
class Solution {
public:
    /**
     * @param num: an integer
     * @return: an integer, the number of ones in num
     */
    int countOnes(int num) {
        // write your code here
        int counter = 0;
        while (num) {
            num &= num - 1;
            counter++;
        }
        return counter;
    }
};

这个用法判断是不是2的整数次幂很容易,因为2的整数次幂必然只有1个bit的1。

bool checkPowerOf2(int n) {
    // write your code here
    return n > 0 && ((n & (n - 1)) == 0);
}

Flip Bits

用到了xor的性质。

class Solution {
public:
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    int bitSwapRequired(int a, int b) {
        // write your code here
        int counter = 0;
        int c = a^b;
        for (int i = 0; i < 32; i++) {
            counter += c & 1;
            c >>= 1;
        }
        return counter;
    }
};

A + B problem

这题。 主要利用异或运算来完成。 异或运算有一个别名叫做:不进位加法。 那么a ^ b就是a和b相加之后,该进位的地方不进位的结果。 然后下面考虑哪些地方要进位,自然是a和b里都是1的地方。 a & b就是a和b里都是1的那些位置,a & b << 1 就是进位 之后的结果。所以:a + b = (a ^ b) + (a & b << 1) 。令a’ = a ^ b, b’ = (a & b) << 1 可以知道,这个过程是在模拟加法的运算过程,进位不可能 一直持续,所以b最终会变为0。因此重复做上述操作就可以 求得a + b的值。

class Solution {
    /*
     * param a: The first integer
     * param b: The second integer
     * return: The sum of a and b
     */
    public int aplusb(int a, int b) {
       while (b != 0) {
            int _a = a ^ b;
            int _b = (a & b) << 1;
            a = _a;
            b = _b;
        }
        return a;
    }
};

Update Bits

Given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j) You can assume that the bits j through i have enough space to fit all of M. That is, if M=10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j=3 and i=2, because M could not fully fit between bit 3 and bit 2.

把一个数的 [j, i] 之间的bits 用另一个数去填充。

class Solution {
public:
    /**
     *@param n, m: Two integer
     *@param i, j: Two bit positions
     *return: An integer
     */
    int updateBits(int n, int m, int i, int j) {
        // write your code here
        int right_part = n & ((1 << i) - 1);
        // The behavior of right shift >= 32 is undefined in C++.
        int left_part = j >= 31 ? 0 : (n >> (j + 1)) << (j + 1);
        return left_part | (m << i) | right_part;
    }
};

先用一个 mask 把 i 右边的数给取出来。 左边的数要这么取:先把bits右移 j + 1位,然后再左移 j + 1位,这样右边的数就都清空了。 最后一步把 m 左移后再把左边部分和右边部分用 | 粘起来。 这种思想还可以用来做高地位互换等。把前一半的数右移,把后一半的数左移,然后 | 起来。

swap two variables

如何不用第三个临时变量来交换两个数。

void swap(int &a, int &b){
	if (a != b){
		  a ^= b;
      b ^= a;
      a ^= b;
	}
}

abs

//取符号位
	int a = -100;
	int i = a >> 31;
	//i = 0 正数
	if(i == 0){
		printf("%d\n",a);
	}
	//i = 1 负数
	else{
		printf("%d\n",~a + 1);
	}

Number Complement

class Solution {
public:
    int findComplement(int num) {
        unsigned mask = ~0;
        while (num & mask) mask <<= 1;
        return ~mask & ~num;
    }
};