算法 ---- 位操作小结

programming # algorithm

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

介绍

在计算机的实际操作中，位操作主要用于设备控制，许多Linux下的标志位，网络协议的标志位，差错控制与纠错控制，数据压缩优化，数据加密等等。现代编程语言通常运行程序直接对某些数据进行位操作运算，有时候巧妙使用位操作为使程序变的异常简便。

基础

本文将用到的位操作符包括&(与), |(或), ~(非), ^(异或)和移位符如a << b或a >> b。

符号 描述 运算规则  
& 与 两个位都为1时，结果才为1  
    或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1  
~ 非 0变1，1变0  
« 左移 各二进位全部左移若干位，高位丢弃，低位补0  
» 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）  

位操作符基本用法

  • 并集 A | B
  • 交集 A & B
  • 差集 A & ~B
  • 取反 ~A
  • 设置某个比特位 A |= 1 << bit
  • 清楚某个比特位 A &= ~(1 << bit)
  • 测试某个比特位 (A & 1 << bit) != 0
  • 提取最右为1的比特位 A&-A or A&~(A-1) or x^(x&(x-1))
  • 移除最右为1的比特位 A&(A-1)
  • 得到比特位全为1的数 ~0

以下是关于位操作符的两个简单例子:

  • 计算一个数以二进制表示时包含1的个数

    int count_one(int n) {
    while(n) {
    n = n&(n-1);
    count++;
    }
    return count;
    }

  • 检验一个数是否是4的幂

    bool isPowerOfFour(int n) {
    return !(n&(n-1)) && (n&0x55555555);
    //check the 1-bit location;
    }

^ 的使用技巧

使用异或^可以移除出现偶数次的比特而保留出现过奇数次的比特，也可以用来保留不同的比特而移除相同的比特。

两个例子：

  • SUM OF TWO INTEGERS

使用^和&实现两个数相加

int getSum(int a, int b) {  
    return b==0? a:getSum(a^b, (a&b)<<1);  
    //be careful about the terminating condition;  
}
  • MISSING NUMBER

一个包含 0, 1, 2, …, n的数组, 找出连续数字中漏掉的一个. 比如说对于数组[0, 1, 3]，返回 2。

int missingNumber(vector<int>& nums) {  
    int ret = 0;  
    for(int i = 0; i < nums.size(); ++i) {  
        ret ^= i;  
        ret ^= nums[i];  
    }  
    return ret^=nums.size();  
}

| 的使用技巧

|用于尽可能的保留所有1比特。

  • 找出比指定数字小的最大2的幂次方

    long largest_power(long N) {
    //changing all right side bits to 1.
    N = N | (N»1);
    N = N | (N»2);
    N = N | (N»4);
    N = N | (N»8);
    N = N | (N»16);
    return (N+1)»1;
    }

  • REVERSE BITS – 翻转32比特的无符号数

    uint32_t reverseBits(uint32_t n) {
    unsigned int mask = 1«31, res = 0;
    for(int i = 0; i < 32; ++i) {
    if(n & 1) res |= mask;
    mask »= 1;
    n »= 1;
    }
    return res;
    }
    uint32_t reverseBits(uint32_t n) {
    uint32_t mask = 1, ret = 0;
    for(int i = 0; i < 32; ++i){
    ret «= 1;
    if(mask & n) ret |= 1;
    mask «= 1;
    }
    return ret;
    }

& 的使用技巧

选择指定位置的比特

反转整数的比特值：

x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);  
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);  
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);  
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);  
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);

BITWISE AND OF NUMBERS RANGE

给定范围[m, n]使得 0 <= m <= n <= 2147483647, 返回范围内所有值按位的与操作之和。例如给定 [5, 7], 返回4.

int rangeBitwiseAnd(int m, int n) {  
    int a = 0;  
    while(m != n) {  
        m >>= 1;  
        n >>= 1;  
        a++;  
    }  
    return m<<a;  
}

NUMBER OF 1 BITS

求一个整数的转为二进制后含有1的比特位的个数（也称为汉明距离)

int hammingWeight(uint32_t n) {  
	int count = 0;  
	while(n) {  
		n = n&(n-1);  
		count++;  
	}  
	return count;  
}  
int hammingWeight(uint32_t n) {  
    ulong mask = 1;  
    int count = 0;  
    for(int i = 0; i < 32; ++i){ //31 will not do, delicate;  
        if(mask & n) count++;  
        mask <<= 1;  
    }  
    return count;  
}