算法 ---- 位操作小结

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

介绍

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

基础

本文将用到的位操作符包括&(与), |(或), ~(非), ^(异或)和移位符如a << ba >> 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;
}