2.4 快速位算法

位运算符

  • & 位与： 0 & 0 = 0 ; 0 & 1 = 0 ; 1 & 0 = 0 ;1 & 1 = 1 ; 同为 1 时， 结果为 1。
  • | 位或： 0 | 0 = 0 ; 0 | 1 = 1 ; 1 | 0 = 1 ;1 | 1 = 1 ; 存在 1 时， 结果为 1。
  • ^ 位异或： 0 & 0 = 0 ; 0 & 1 = 1 ; 1 & 0 = 1 ;1 & 1 = 0 ; 值相异时， 结果为 1。
  • ~ 位反： ~ 0 = 1 ; ~ 1 = 0 ;
  • « 左移:
  • >> 逻辑右移：
  • >» 算术右移：

位运算特性

与（&）运算

一个数n与0进行与运算，值为0，n & 0 = 0。
一个数n与-1进行与运算，值为n，n & -1 = n。
一个数n与自己进行与运算，值为n，n & n = n。

或（|）运算

一个数n与0进行或运算，值为n，n | 0 = n。
一个数n与-1进行或运算，值为-1，n | -1 = -1。

非（~）运算

对二进制的每一位都按位取反。
对于数n，n + (~n) = -1。

异或（^）运算

运算的二进位结果，相异为1，相同为0。

一个数n与0异或，值为n，n ^ 0 = n。
一个数n与-1异或，值为~n，n ^ -1 = ~n。
一个数n与自己异或，值为0，n ^ n = 0。

左移（«）和右移（»）运算

向左进行移位操作，高位丢弃，低位补 0
向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位

应用

快速位算法 的子部分

4.1 快速平均值

符号定义

  • a :待运算的值
  • b :待运算的值
  • r :运算结果

计算

r = (a + b) >> 1

总结

>> 1 ,相当于 除 2。

4.2 位域值提取

位域定义

C语言中的位域定义：

struct Bits{
    uint32_t b2:2;
    uint32_t b4:4;
};

提取位域定义的值算法如下：

符号定义：

  • w :定义的位宽，如 b2 的位宽为 2 bit；
  • p :位域字段的位偏移，如 b2 的位偏移为 0，b4 的位偏移为 2；
  • v :位域字段所在的整体数据值，如 b2 就在 uint32_t 的数据上；
  • r :计算的结果；

第1步：计算位域掩码

mask = (1 << w) - 1

第2步：逻辑右移

tv = v >> p

第3步：截取域至

v = tv & mask

总结

r = (v >> p) & ( (1 << w) - 1)

如果v是有符号数，就需要进行符号扩展。

符号扩展

第1步：计算符号掩码

smask = 1 << (w-1)

第2步：计算符号位值

signed = r & smask

第3步：符号扩展

signed != 0 ? ( r = r | (-1 « w) ) : r

总结

( (1 « (w-1)) & r) != 0 ? ( r = r | (-1 « w) ) : r

4.3 INT_MAX和INT_MIN

假设

假设您有一个 32 位系统：

  • INT_MAX是 01111111111111111111111111111111 ；
  • INT_MIN是 10000000000000000000000000000000 ；

0 和 1 分别位于最高有效位位置，分别表示符号位。

计算INT_MAX和INT_MIN 在 C/C++ 中： 数字 0 表示为 000…000（32个）。

原理

我们计算 0 的 NOT 得到一个有 32 个 1 的数字。这个数字不等于INT_MAX因为符号位是1，即负数。 现在，这个数字的右移将产生011…111 这是INT_MAX。 将INT_MAX 按位取反 就得到INT_MIN。

代码

unsigned int max = 0;
 
max = ~max;
max = max >> 1;
     
int min = ~max;

4.4 应用 n + (~n) = -1

原理

设整数 n 类型为 int_8，值为 3，则 3 + (~3) = 0000 0011 + 1111 1100 = 1111 1111 = -1，所以引出非运算的基础公式 n + (~n) = -1，也可以将 n ^ -1 = ~n 带入。

位运算实现n+1与n-1

对n + (~n) = -1进行等式变换可得：

int n;
~n = -(n + 1);
n + 1 = -~n;
n - 1 = ~-n;	// 假设n = -n，可推出此等式

取相反数

一个数的相反数等于其按位取反后再加1，对上等式变换推出：

int n;
-n = ~n + 1;

取绝对值

这一块内容也用到了n ^ 0 = n 和 n ^ -1 = ~n：

  • 若 n 为非负数，则 n » 31 = 0，所以 abs = n ^ 0 - 0 = n。
  • 若 n 为负数，则 n » 31 = -1，所以 abs = n ^ (-1) + 1 = ~n + 1 = -1 - n + 1 = -n。
int abs, n;
abs = (n ^ (n >> 31)) - (n >> 31)

4.5 应用 n ^ n = 0 和 n ^ 0 = n

交换两个数的值

不需要第三个临时变量，交换两个数的值

 int a, b;
 a ^= b;	// a = a ^ b;
 b ^= a;	// b = b ^ a = b ^ a ^ b = (b ^ b) ^ a = 0 ^ a = a
 a ^= b;	// a = a ^ b = a ^ a ^ b = 0 ^ b = b

代替特定的条件赋值

如果 x = a，则 a ^ b ^ x = 0 ^ b；如果 x = b，则 a ^ b ^ x = 0 ^ a；

所以下列代码可等价于：x = a ^ b ^ x。

int a, b, x;

if(x == a) 
    x = b;
else if(x == b)
    x = a;
    
// 上面代码等价于
x = a ^ b ^ x

4.6 应用 x&(x-1)

原理

x&(x-1)可以消除数字x二进制表示的最后一个1，如：

int x = 0xf6;
printf("%x\n", x);		//0b11110110 
printf("%x\n", x&(x-1));	//0b11110100

判断一个正数是不是2的次幂

如果一个正数是2的次幂，则这个数的二进制表示中只含有一个1。

int x;
if(x&(x-1)){
	//x至少含有两个1，所以不是2的次幂
}

计算一个数的二进制含有多少个1

x中的最后一个1可以通过操作x = x&(x-1)循环消去，当最后x值为0时，便可以求出二进制中1的个数。

int x, total;
while(x > 0){ 
	x = x&(x-1);
    total++;
}

4.7 应用 2的次方

整数对2的乘/除法

整数 n 向右移一位，相当于将 n 除以 2；数 n 向左移一位，相当于将 n 乘以 2。

int n = 2;
n >> 1; // 1
n << 1; // 4

n 对“2的次方”取余

m 是2的次方，则其二进制数只有一个1，如 4 => 0100，8 => 1000。m-1 之后，原本 m 二进制的1变成0，原本1后面的0全变成1，如 4-1 = 3 => 0011，8-1 = 7 => 0111。

2 ^ 0 = 1

2 ^ 1 = 2

2 ^ 2 = 4

2^ 3 = 8

2 ^ 4 = 16

2 ^ 5 = 32

…

可以看出 2^(q + 1) 永远都是 2^q 的整数倍，而 2^q 比 2^(q - 1)+2^(q - 2) … + 2^0 的和还要大 1。

假设 m = 2^q ，q 为正整数。n 的二进制数中，第[ n 的最高位, q ]位的和是 m 的整数倍，而第[ q-1, 0 ]位的和是 n/m 的余数，也就是说将n的二进制数的第[ q-1, 0 ]位截取，即可得到 n/m 的余数。

m = 2^q ， m − 1 = 2^(q - 1)+2^(q - 2) … + 2^0 => 00011…1（[ q-1, 0 ]位全为1），所以 n & (m - 1) 的值为 n/m 的余数。

int mod, n, m; // m是2的次方，如4,8等
mod = n & (m - 1);

将 n 以“2的次方”倍数最小补全

有 n 和 m 两数，m 为2的次方，找到大于等于 n 且正好是 m 整数倍的最小数。

假设 m = 2^q ，则 m 的倍数的二进制数中，第 q 位为1，其余位全为 0；(m - 1) 的二进制数中[ q-1, 0 ]位全为 1，其余位全为 0。

所以有两种情况：

  • 如果n的二进制数中[ q-1, 0 ]位全为 0，则 n 就是 m 整数倍的最小数；
  • 如果n的二进制数中[ q-1, 0 ]位不全为 0，在第 q 位上加 1，所得结果就是 m 整数倍的最小数。

现给 n 加上一个[ q-1, 0 ]位全为 1，其余位全为 0 的数（ m-1 就是这个数），并将所得结果的[ q-1, 0 ]位全部置为 0（结果与 ~(m - 1) 相与即可），便可满足这两种情况。

int min, n, m;
min = (n + m - 1) & ~(m - 1);

4.8 取两数的最 大/小 值

原理

  • 如果 a >= b，则 a - b >= 0 且 (a - b) < 0，所以 ((a - b) » 31) = 0 且 ((a - b) » 31) = -1。
  • 如果 a < b，则 a - b < 0 且 (a - b) >= 0，所以 ((a - b) » 31) = -1 且 ((a - b) » 31) = 0。

实现

int max(int a, int b){
    return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
}

int min(int a, int b){
    return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31));
}

4.9 循环移位

循环左移

以32位整数为例，循环左移的过程可以分为3步：

  1. 将 x 左端的 n 位先移动到 y 的低 n 位中，x » (32-n);
  2. 将 x 左移 n 位，其右面低位补 0，x«n;
  3. 进行按位或运算(x » (32 - n) | (x « n));

循环右移

以32位整数为例，循环右移的过程可以分为3步：

  1. 将 x 的左端的低 n 位先移动到 y 的高 n 位中 x « (32 - n)
  2. 将 x 右移 n 位，其左面高 n 位补 0，x » n;
  3. 进行按位或操作(x « (32 - n) | (x » n));

总结

假如将一个无符号的数据 val ，长度为 N bit，需要循环移动 n bit。可以利用下面的公式：

循环左移：(val >> (N - n) | (val << n))
循环右移：(val << (N - n) | (val >> n))
  • 注：n ->[0,N-1],所以 在运算之前,将 n 映射到该范围： n = n & ( N - 1 )

实现

//循环左移
unsigned int ROL(unsigned int val,unsigned int n){
    n&=31;
    return  (val >> (32 - n) | (val << n));
}
//循环右移
unsigned int ROL(unsigned int val,unsigned int n){
    n&=31;
    return  (val << (32 - n) | (val >> n));
}