C++位运算常见操作

一些位运算的常见操作，整理如下：

注意：
位运算操作符的优先级都非常低，尽量记得加括号。

1. 给第n位(从右边开始数，初始位置0)值置1

int set_bit(int x, int n){ return x |= (1 << n); }

2. 清除第n位(从右边开始数，初始位置0)

int clear_bit(int x, int n){ return x &= ~ (1 << n); }

3. 得到第n位(从右边开始数，初始位置0)

bool get_bit(int x, int n){ return x & (1 << n); }

注意：int数字的第n位和string数字的第n位不一样！
int数字 (例如 011100110110001) 的第n位是从右往左数，
string数字 (例如"011100110110001")的第n位通常是从左往右数。

4. a ^ b (异或)是不进位加法，即 a ^ b 相加之后该进位的地方不进位的结果。 a & b 就是a 和 b 里都是1的那些位置。
   一个例子如下:

不用+完成加法的算法：

int aplusb(int a, int b) { while (b) { int a1 = a ^ b; int b1 = (a & b) << 1; a = a1; b = b1; } return a; }

以a=3 (0011)， b=5(0101)为例。
a = 0011 => 0110 => 0100 => 0000 =>1000 (return) //未进位加法和
b = 0101 => 0010 =>0100 => 1000 =>0000 //进位

递归版本如下：

int aplusb(int a, int b) { if (a == 0) return b; if (b == 0) return a; return aplusb((a & b) << 1, a ^ b); }

5. 消去二进制中最右侧的那个1:x & (x - 1)
   一些例子如下：

检查n是否为2的幂次位：

bool checkPowerOf2(int n) { return n > 0 && (n & (n - 1)) == 0; }

计算一个32位整数有多少个1

int countOnes(int num) { int count = 0; while (num) { count++; num &= num - 1; } return count; }

计算a要反转多少位变成b

int bitSwapRequired(int a, int b) { int c = a ^ b; int count = 0; while (c) { count++; c &= c - 1; } return count; }

6. x & (-x) 是x的最右边一个1的位置对应的数 (注意x&(x-1)是将其该位消去)。
   如12 & (-12) 返回4。8 & (-8) 返回8。这个技巧是线段树(Binary Index Tree)算法里面的核心技巧(见Lowbit(x))。

7. 取反操作~
   正整数的按位取反是其本身+1的负数
   A = (1)10 = (00000000000000000000000000000001)2
   ~A = ~ (1)10 = (11111111111111111111111111111110)2 = (-2)10

负整数的按位取反是其本身+1的绝对值
零的按位取反是 -1

8. 基于union的bitmap的操作。

typedef union { int all; struct { int flag0 : 1; //bit 0 int flag1 : 1; //bit 1 int flag2 : 1; //bit 2 ... int flag15 : 1; //bit 15 int rsvd : 16; //bit 16-31 } bits; }cntl_t; #define BIT(x) 1<<((n)) cntl_t cntl;

对flag2的操作如下：

#define clear_flag2() (cntl.bits.all &= ~BIT(2)) #define set_flag2() (cntl.bits.all |= BIT(2)) #define get_flag2() (cntl.bits.flag2)

也可以直接对flag进行读写操作。比如说：

cntl.bibts.flag2 = 3;

下面这个链接对C/C++ bit field的操作说的非常清楚，是一个非常好的链接。
https://aticleworld.com/bit-field-in-c/

9. Gray Code 的生成一种方法是基于i ^ (i << 1)。

10. 负数的移位很重要！
    C/C++中左移是逻辑移位，右端补0，所以负数左移，有可能变成正数；
    C/C++中右移是算数移位，左端补齐最高位的符号位。
    负数右移，肯定还是负数。
    引用https://blog.csdn.net/e3399/article/details/7526230的例子

/********************************************************************** * Compiler: GCC ************************************************************************/ #include <stdio.h> int main(int argc, char **argv) { int i = 0x8000000f; //这里的0x8000000f为int型数据的补码形式 int j = i >> 3; //右移是算术移位，左端补齐的是符号位 int k = i << 1; //左移是逻辑移位，右端补0 printf("%d %x\n", i, i); printf("%d %x\n", j, j); printf("%d %x\n", k, k); i = -9; printf("%d %x\n", i, i); i = 0xfffffff7; j = i >> 3; k = i << 1; printf("%d %x\n", i, i); printf("%d %x\n", j, j); printf("%d %x\n", k, k); return 0; }

Output:
-2147483633 8000000f
-268435455 f0000001
30 1e
-9 fffffff7
-9 fffffff7
-2 fffffffe
-18 ffffffee

注意：
-9 << 1 = -18, 并不是乘2这么简单。
-9的补码是0xffffffff7，<<1后变成0xffffffEE，即1111…1110 1110
此即-18的补码。

11. 用16进制的形式对数据进行赋值，这16进制的数代表的是补码
    补码：负数的补码是在其原码的基础上,符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
    [+1] = [00000001]原 = [00000001]反 = [00000001]补
    [-1] = [10000001]原 = [11111110]反 = [11111111]补

i = 0xfffffff7; //0xfffffff7是补码，而不是原码，故i = -9 printf("%d %x\n", i, i); i = -9; printf("%d %x\n", i, i); //故两个printf输出结果相同

12）取模运算可以用：
a % b = a - (a / b) * b
如果b为2的n次方，可用
a % b = a & (b - 1)

13. 2147483648实际上是存的-2147483648?
    因为
    2147483647 = 01111111 11111111 11111111 11111111
    -2147483647表示为(2的补码)
    10000000 00000000 00000000 00000001
    -2147483648(2的补码)还可以比-2147483647少1，所以是
    10000000 00000000 00000000 00000000
    另外，实际上补码的补码就是原码(数的原始表示)
    所以10000000 00000000 00000000 00000000 的补码是
    11111111 11111111 11111111 11111111 + 1，第一个1是负号，所以
    1111111 11111111 11111111 11111111 + 1 = 10000000 00000000 00000000 00000000=2147483648，这里第一个1是实际数字。加上负号，即-2147483648。
    另外，11111111,11111111,11111111,11111111看起来很大，实际上是存的-1。

14. 位运算如果和硬件结合起来会更快。
    比如说ARM芯片支持__clz()内置函数，返回某无符号整数的前置0的个数。

Syntax: unsigned char __clz(unsigned int val) Return value The __clz intrinsic returns the number of leading zeros in val.

有了__clz()函数，我们就可以定义下面的MSB(x)宏来返回MSB比特(即从高到低第一个1)的位置。

#define MSB(x) (31- __clz((unsigned int)x))

注意这里默认一个unsigned int占4个字节。
用下面的循环我们可以快速遍历一个unsigned int (即下面的bitmap)的1，注意while里面的操作次数就是bitmap里面的1比特的个数。

unsigned int bitmap = 0x1234; while (bitmap) { int pos = MSB(bitmap); //do something bitmap &= ~(0x1<< pos); }

15. 如果n是2^k，那么x % n = x & (n - 1)，显然后者更快。
    比如说33 % 8 = 33 & 7 = 1, 37 % 8 = 37 & 7 = 5

16. Round up to the next highest power of 2
    from https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2

unsignedintv;// compute the next highest power of 2 of 32-bit vv--;v|=v>>1;v|=v>>2;v|=v>>4;v|=v>>8;v|=v>>16;v++;

从一个整数中提取 [start, start + width) bit field，意思是：
从 bit start 开始
一共提取 width 个 bits
bit 编号从最低位 0 开始
核心公式：
field = (value >> start) & mask;
其中：
mask = (1U << width) - 1U;

Example:
value = 1101 0110
提取：
[start, start + width) = [2, 6)
也就是 bit [5:2]：
value = 11 0101 10
↑↑↑↑
bits 5:2 = 0101
代码：
uint32_t value = 0xD6U; /* 1101 0110 */
unsigned start = 2;
unsigned width = 4;
uint32_t mask = (1U << width) - 1U;
uint32_t field = (value >> start) & mask;

value >> 2 = 0b1101 0110 >> 2 = 0b0011 0101
mask = 0b00001111
field == (value >> start) & mask = 0b0101 = 5