位運算的一般應用
| 功能 | 例子 | 運算 |
|---|---|---|
| 去掉最后一位 | 1110101->111010 | x>>1 |
| 在最后加0 | 1110101->11101010 | x<<1 |
| 在最后加1 | 1110101->11101011 | x<<1+1 |
| 最后一位變成1 | 111010->111011 | x|1 |
| 最后一位變成0 | 111011->111010 | x|1-1 |
| 最后一位取反 | 1110101->1110100 | x^1 |
| 右數第k位設為1 | 1110101->1111101,k=4 | x|(1<<(k-1)) |
| 右數第k位設為0 | 1110101->1110001,k=3 | x&~(1<<(k-1)) |
| 右數第k位取反 | 1110101->1111101,k=4 | x^(1<<(k-1)) |
| 取末尾k位 | 1110101->101,k=3 | x&(1<<k-1) |
| 取右數第k位 | 1110101->1,k=5 | x>>(k-1)&1 |
| 把末尾k位變成1 | 1110101->1110111,k=3 | x|(1<<k-1) |
| 把末尾k位變成0 | 1110101->1110000,k=3 | x&(1<<k) |
| 把末尾k位取反 | 1110101->1110010,k=3 | x^(1<<k-1) |
| 把右邊連續的1變成0 | 1101111->1100000 | x&(x+1) |
| 把右邊連續的0變成1 | 1010000->1011111 | x|(x-1) |
| 把右數第一個0變成1 | 10101101->10101111 | x|(x+1) |
| 取右邊連續的1 | 10101111->1111 | (x^(x+1))>>1 |
| 取最右邊的1 | 10010->10 | x&(~x+1) |
| 去掉右數第一個1的左邊 | 10010100->100 | x&(x^(x-1)) |
通過如下的例子，來看看位運算在底層的應用：
1.判斷是否是2的整數次冪(來自Linux kernel)
uint32_t is_power_two(uint32_t x){
return !(x&(x-1));
}
uint32_t is_power_two(uint32_t x){
return x==x&~x+1;
}
方法一
對于無符號數的編碼，可以做出如下解釋:
\[x=\sum _{i=0} ^{w-1} x_i *2^i \]
顯然,若該數是2的整數次冪,顯然二進制形式是[00...0100...0]的形式,設第k位為1(從第0位計數),則有:
\[x-1=2^k-1=\sum_{i=0}^{k-1}2^i \]
顯然,該數的表達方式為[00...00111...1],與原數進行按位與,結果為0.
方法二
x&~x+1即x&-x,首先關于補碼的非運算.任意非0的x總可以找到最后邊的1,即可以將x表示為:
\[[x_{w-1},x_{w-2},...,x_{k+1},1,0,0,...,0] \]
從而有:
\[-x=[～ x_{w-1},～x_{w-2},...,～x_{k+1},1,0,0,...,0] \]
顯然,若x是2的整數次冪則有x==x&-x為真.
2.對2的整數次冪取余(來自HashMap)
uint32_t mod_power_two(uint32_t x,uint32_t bucket){
return x&(bucket-1);
}
對于一個無符號數x,xmod2^w的作用等價于丟掉該數二進制表示的從w+1位開始的高位,即將該二進制數進行類似截斷.例如:
\[25\% 16=9--->11001\&01111=01001_2=9_{10} \]
16=2^4,因此取余會將第5位開始的位均設為0,只保留后4位,因此:
\[x\ mod\ 2^n=x\&(2^n-1) \]
3.向上取整到2的整數次冪
uint32_t next_power_two(uint32_t x){
--x;
x|=x>>1;
x|=x>>2;
x|=x>>4;
x|=x>>8;
x|=x>>16;
return ++x;
}
--x是為了保證,這個數不是2的整數次冪. 設這個數可以表示為1.....,則右移1位得01......或運算得11......,繼續右移2位,得0011......或運算得1111......,最后一次位運算后得111...111最后回傳時+1遍得到了向上的一個2的整數次冪.
4.判斷是否含有奇數個1
bool is_oddones(uint32_t x){
x^=x>>1;
x^=x>>2;
x^=x>>4;
x^=x>>8;
x^=x>>16;
return x&0x1;
}
總的思想:奇數個1進行異或結果位1,因為只需想方法,將這個數二進制位的所有數進行異或就知道是否有奇數個1了.舉了例子,下面這個 數是某個數二進制的低幾位.
第一次運算:
? 1110 1101 1000
? 0111 0110 1100
^------------------------------
? 1001 1011 0100
最右邊的0是第0位與第1位異或所得,依次可得 從右往左位 0^1 1^2 2^3 3^4.....(此處的數字為第位數,下同)
第二次運算:
? 1001 1011 0100
? 0010 0110 1101
^-----------------------------
? 1011 1101 1001
第二排數字的結果分別是2^3 3^4 4^5 5^6...,故最右邊的0是0^1^2^3,依次再有1^2^3^4,...
第三次運算:
? 1011 1101 1001
? 1011 1101
^-----------------------------
? 0110 0100
第二排的數字從最右邊開始為 4^5^6^7,依次.......從而結果中,最右邊的數代表0^1^2^3^4^5^6^7
因而,若原數字在原始資料中是第i位,在最終的結果中,該位代表的即是:
\[i\oplus (i+1)\oplus (i+2)\oplus \cdots \oplus (i+30)\oplus (i+31) \]
因為,令i=0,即最低位的值,即為結果,故最終x&0x1
5. 1的個數
uint32_t count_one(uint32_t x){
x=(x&0x55555555)+(x>>1&0x55555555);
x=(x&0x33333333)+(x>>2&0x33333333);
x=(x&0x0f0f0f0f)+(x>>4&0x0f0f0f0f);
x=(x&0x00ff00ff)+(x>>8&0x00ff00ff);
x=(x&0x0000ffff)+(x>>16&0x0000ffff);
return x;
}
思想:分而治之
先將32位數分成16份,每份倆部分:
0x55555555=0101......01
故x&0x55555555得到每個小份的第二部分的1情況,x>>1&0x55555555得到每個小份中第一部分的1的情況,相加得到的2位二進制數即為,該小份中1的個數.現在的任務就是將這些數都加起來 .
? 10 11 01 00 ......
第一次 01 10 01 00
0x33333333=0011......0011
故x&0x33333333將每個2位能單獨拿出來,再加上x>>2&0x33333333就是兩個2位數的和(是一個用4位二進制表示的數),即將這16份,合并成8份,4位一組.
? 01 10 01 00
第二次 0011 0001
0x0f0f0f0f=00001111...00001111
故x&0x0f0f0f0f將4位單獨拿出來,再加上x>>4&0x0f0f0f0f就是兩個4位數的和.按照這種思想,最后會得到兩個16位數的和(按32位表示)這個數的大小就是1的個數.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/33852.html
標籤：其他