一些位運(yùn)算的常見操作整理如下注意位運(yùn)算操作符的優(yōu)先級(jí)都非常低盡量記得加括號(hào)。給第n位(從右邊開始數(shù)初始位置0)值置1int set_bit(int x, int n){ return x | (1 n); }清除第n位(從右邊開始數(shù)初始位置0)int clear_bit(int x, int n){ return x ~ (1 n); }得到第n位(從右邊開始數(shù)初始位置0)bool get_bit(int x, int n){ return x (1 n); }注意int數(shù)字的第n位和string數(shù)字的第n位不一樣int數(shù)字 (例如 011100110110001) 的第n位是從右往左數(shù)string數(shù)字 (例如011100110110001)的第n位通常是從左往右數(shù)。a ^ b (異或)是不進(jìn)位加法即 a ^ b 相加之后該進(jìn)位的地方不進(jìn)位的結(jié)果。 a b 就是a 和 b 里都是1的那些位置。一個(gè)例子如下:不用完成加法的算法int aplusb(int a, int b) { while (b) { int a1 a ^ b; int b1 (a b) 1; a a1; b b1; } return a; }以a3 (0011) b5(0101)為例。a 0011 0110 0100 0000 1000 (return) //未進(jìn)位加法和b 0101 0010 0100 1000 0000 //進(jìn)位遞歸版本如下int aplusb(int a, int b) { if (a 0) return b; if (b 0) return a; return aplusb((a b) 1, a ^ b); }消去二進(jìn)制中最右側(cè)的那個(gè)1:x (x - 1)一些例子如下檢查n是否為2的冪次位bool checkPowerOf2(int n) { return n 0 (n (n - 1)) 0; }計(jì)算一個(gè)32位整數(shù)有多少個(gè)1int countOnes(int num) { int count 0; while (num) { count; num num - 1; } return count; }計(jì)算a要反轉(zhuǎn)多少位變成bint bitSwapRequired(int a, int b) { int c a ^ b; int count 0; while (c) { count; c c - 1; } return count; }x (-x) 是x的最右邊一個(gè)1的位置對(duì)應(yīng)的數(shù) (注意x(x-1)是將其該位消去)。如12 (-12) 返回4。8 (-8) 返回8。這個(gè)技巧是線段樹(Binary Index Tree)算法里面的核心技巧(見Lowbit(x))。取反操作~正整數(shù)的按位取反是其本身1的負(fù)數(shù)A (1)10 (00000000000000000000000000000001)2~A ~ (1)10 (11111111111111111111111111111110)2 (-2)10負(fù)整數(shù)的按位取反是其本身1的絕對(duì)值零的按位取反是 -1基于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;對(duì)flag2的操作如下#define clear_flag2() (cntl.bits.all ~BIT(2)) #define set_flag2() (cntl.bits.all | BIT(2)) #define get_flag2() (cntl.bits.flag2)也可以直接對(duì)flag進(jìn)行讀寫操作。比如說cntl.bibts.flag2 3;下面這個(gè)鏈接對(duì)C/C bit field的操作說的非常清楚是一個(gè)非常好的鏈接。https://aticleworld.com/bit-field-in-c/Gray Code 的生成一種方法是基于i ^ (i 1)。負(fù)數(shù)的移位很重要C/C中左移是邏輯移位右端補(bǔ)0所以負(fù)數(shù)左移有可能變成正數(shù)C/C中右移是算數(shù)移位左端補(bǔ)齊最高位的符號(hào)位。負(fù)數(shù)右移肯定還是負(fù)數(shù)。引用https://blog.csdn.net/e3399/article/details/7526230的例子/********************************************************************** * Compiler: GCC ************************************************************************/ #include stdio.h int main(int argc, char **argv) { int i 0x8000000f; //這里的0x8000000f為int型數(shù)據(jù)的補(bǔ)碼形式 int j i 3; //右移是算術(shù)移位左端補(bǔ)齊的是符號(hào)位 int k i 1; //左移是邏輯移位右端補(bǔ)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 f000000130 1e-9 fffffff7-9 fffffff7-2 fffffffe-18 ffffffee注意-9 1 -18, 并不是乘2這么簡(jiǎn)單。-9的補(bǔ)碼是0xffffffff71后變成0xffffffEE即1111…1110 1110此即-18的補(bǔ)碼。用16進(jìn)制的形式對(duì)數(shù)據(jù)進(jìn)行賦值這16進(jìn)制的數(shù)代表的是補(bǔ)碼補(bǔ)碼負(fù)數(shù)的補(bǔ)碼是在其原碼的基礎(chǔ)上,符號(hào)位不變, 其余各位取反, 最后1. (即在反碼的基礎(chǔ)上1)[1] [00000001]原 [00000001]反 [00000001]補(bǔ)[-1] [10000001]原 [11111110]反 [11111111]補(bǔ)i 0xfffffff7; //0xfffffff7是補(bǔ)碼而不是原碼故i -9 printf(%d %x\n, i, i); i -9; printf(%d %x\n, i, i); //故兩個(gè)printf輸出結(jié)果相同12取模運(yùn)算可以用a % b a - (a / b) * b如果b為2的n次方可用a % b a (b - 1)2147483648實(shí)際上是存的-2147483648?因?yàn)?147483647 01111111 11111111 11111111 11111111-2147483647表示為(2的補(bǔ)碼)10000000 00000000 00000000 00000001-2147483648(2的補(bǔ)碼)還可以比-2147483647少1所以是10000000 00000000 00000000 00000000另外實(shí)際上補(bǔ)碼的補(bǔ)碼就是原碼(數(shù)的原始表示)所以10000000 00000000 00000000 00000000 的補(bǔ)碼是11111111 11111111 11111111 11111111 1第一個(gè)1是負(fù)號(hào)所以1111111 11111111 11111111 11111111 1 10000000 00000000 00000000 000000002147483648這里第一個(gè)1是實(shí)際數(shù)字。加上負(fù)號(hào)即-2147483648。另外11111111,11111111,11111111,11111111看起來很大實(shí)際上是存的-1。位運(yùn)算如果和硬件結(jié)合起來會(huì)更快。比如說ARM芯片支持__clz()內(nèi)置函數(shù)返回某無符號(hào)整數(shù)的前置0的個(gè)數(shù)。Syntax: unsigned char __clz(unsigned int val) Return value The __clz intrinsic returns the number of leading zeros in val.有了__clz()函數(shù)我們就可以定義下面的MSB(x)宏來返回MSB比特(即從高到低第一個(gè)1)的位置。#define MSB(x) (31- __clz((unsigned int)x))注意這里默認(rèn)一個(gè)unsigned int占4個(gè)字節(jié)。用下面的循環(huán)我們可以快速遍歷一個(gè)unsigned int (即下面的bitmap)的1注意while里面的操作次數(shù)就是bitmap里面的1比特的個(gè)數(shù)。unsigned int bitmap 0x1234; while (bitmap) { int pos MSB(bitmap); //do something bitmap ~(0x1 pos); }如果n是2^k那么x % n x (n - 1)顯然后者更快。比如說33 % 8 33 7 1, 37 % 8 37 7 5Round up to the next highest power of 2from https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2unsignedintv;// compute the next highest power of 2 of 32-bit vv--;v|v1;v|v2;v|v4;v|v8;v|v16;v;從一個(gè)整數(shù)中提取 [start, start width) bit field意思是從 bit start 開始一共提取 width 個(gè) bitsbit 編號(hào)從最低位 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 0101mask 0b00001111field (value start) mask 0b0101 5