位运算 – 老虫儿的笔记本

补码
- 32位无符号整数int：直接把这32位编码看作32位二进制数N
- 32位有符号整数int：
  - 以最高位位符号位，0表示非负数，1表示负数。
  - 对于最高位为0的每种编码C，直接看作32位二进制数S。
  - 定义该编码按位取反后得到的编码~C表示的数值为-1-S。
  - 可以发现在补码下每个数值都有唯一的表示方式，并且任意两个数值做加减法运算，都等价于在32位补码下做最高位不进位的二进制加减法运算。
  - 发生溢出时，32位无符号整数自动对2^32取模。
移位运算
- 左移：1<<n=2的n次方， n<<1=2n
- 算术右移n>>1=n/2.0 (向下取整，高位以符号位填充)
- 逻辑右移（高位以0填充）
二进制状态压缩
- 取出整数n在二进制表示下的第k位 (n>>k)&1
- 取出整数n在二进制表示下的第0~k-1位（后k位） n&((1<<k)-1）
- 把整数n在二进制表示下的第k位取反 n xor (1<<k)
- 对整数n在二进制表示下的第k位赋值为1 n|(1<<k)
- 对整数n在二进制表示下的第k位赋值位0 n&(~(1<<k))
成对变换
- 对于非负整数n：
  - n为偶数：n xor 1等于n+1
  - n为奇数：n xor 1等于n-1
lobit运算：
- - lowbit(n)第一位非负整数n在二进制表示下“最低为的1及后面所有的0”构成的数值。例如n=10的二进制数表示为1010，则lowbit（n）=10
  - 推导lowbit公式：n取反加一再或上n —》 lowbot(n)=n&(~n+1)=n&(-n)
  - 配合hash表找出整数二进制下所有是1的位
    - 不断令n=n-lowbit(n)直到n为0,记录其中剪掉的数并对其取对数即可
    - C++数学库比较渣，所以我们选择用hash方法代替log运算,建立一个数组H，令 $H[2^{k}]=k$
    - ```
    const MAXN=1 << 20;//其实是一个标记数组
    int H[MAXN+1];
    for(int i=0; i<=20; i++) H[1 << i]=i;
    while(cin>>n){
    	while(n>0){
    		cout<<H[n & -n]<<' ';
    		n-=n & -n; 
    	}
    	cout<<endl;
    }
```
- 稍微复杂但更高效的方法是建立一个长度为37的数组H，令 $H[2^{k} mod 37]=k$ ,这里有一个小技巧，所有在0~35之间的整数k，2的k次方mod37互不相等，且恰好取编1~36
- ```
int H[37];
for(int i=0;i<36;i++) H[(1ll << i) % 37]=i;
while(cin>>n){
	while(n>0){
		cout<< H[(n & -n) %37] <<' ';
		n -= n & -n;
	}
	cout<<endl;
}
```

发表评论 取消回复

发表评论取消回复