位運算小技巧

位運算的一些小技巧，C語言描述，翻譯自bithacks

計算一個整數(shù)（integer）的符號

int v;  //我們想計算的數(shù)
int sign;  //結(jié)果
//CHAR_BIT是每個字節(jié)的位數(shù)，一般為8
sign = -(v < 0);//if v<0 then -1,else 0;
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// 更高效（可移植性低）
sign = v >> (sizeof(int) * CHAR_BIT - 1);

上面最后一個語句使用右移31位計算了一個32位整數(shù)的符號位，這種做法要比第一種做法更快。當(dāng)有符號位的整數(shù)右移時，左側(cè)的位被復(fù)制到其他位。當(dāng)為負(fù)數(shù)時，最左側(cè)的位為1，正數(shù)為0，負(fù)數(shù)右移31位過后，所有的位數(shù)都為1，所以得到-1，不過這種做法依賴已具體的架構(gòu)。
另外，如果比較喜歡用-1和+1來表示，可以這樣做:

sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1));  // if v < 0 then -1, else +1

如果喜歡-1,0,+1表示：

sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then 0, else 1

檢測兩個整數(shù)符號位是否不同

int x, y;  // 兩個要比較符號位的值

bool f = ((x ^ y) < 0); //當(dāng)且僅當(dāng)符號位不同時為true

注：上面代碼中的bool類型為C99標(biāo)準(zhǔn)新引入，在編寫代碼時需要添加#include <stdbool.h>頭文件

不使用分支計算一個整數(shù)的絕對值

int v;  //要計算絕對值的數(shù)
unsigned int r;  //結(jié)果
int const mask = v >> sizeof(int) * CHAR_BIT -1;

r = (v + mask) ^ mask;

一些cpu沒有整數(shù)絕對值指令（或者是編譯器無法使用）。分支指令的代價較高，上面的語句比一般的做法要好，比如：r=(v<0)?-(unsigned)v:v，即使操作數(shù)目相同。

不使用分支計算兩個整數(shù)的最大值或最小值

int x, y;
int r;

r = y ^ ((x ^ y)) & - (x < y);  //min(x, y)

在某些罕見的機器上，分支的代價很高并且沒有條件移動指令，上面的語句業(yè)余會比常見得做法好，比如：r = (x < y) ? x : y，盡管多了兩條指令

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

計算一個整數(shù)是否是2的倍數(shù)

unsigned int  v;
bool f;

f = (v & (v-1)) ==0;

在這里0也被計算為2的倍數(shù)，解決：

f = v && !(v & (v - 1));

從一個恒定的位寬中擴展符號

注：符號擴展wiki ,關(guān)于符號擴展
對于內(nèi)置類型，符號擴展是自動的，比如說字符型和整型。但假設(shè)有一個帶符號的二進制補碼x，只用b位來儲存，我們想把x轉(zhuǎn)換為一個int型，超過了b位。當(dāng)x是正數(shù)時，只需要進行簡單的復(fù)制，但如果是負(fù)數(shù)，就必須擴展符號。比如，我們只用4位來存儲一個數(shù)字，那么-3用二進制表示就是1101，若用8位，那么-3是11111101。當(dāng)我們轉(zhuǎn)化為更多位表示時，高4位直接被復(fù)制到目的地中，這是就符號擴展。在C語言中，恒定位寬的符號擴展是微不足道的，因為可以在結(jié)構(gòu)體或者聯(lián)合體中指定位字段。比如，將5位轉(zhuǎn)化為一個完整的整數(shù)。

int x;  //將此數(shù)從5位轉(zhuǎn)化為int
int r;  //結(jié)果
struct {signed int x:5} s;
r =s.x = x;

下面是一個C++模板函數(shù)，它使用相同的語言功能在一個操作（盡管編譯器會做更多）中從B位進行轉(zhuǎn)換

template <typename T, unsigned B>
inline T signextend(const T x)
{
  struct {T x:B;} s;
  return s.x = x;
}

int r = signextend<signed int,5>(x);

從可變位寬中擴展符號

有時我們需要擴展一個數(shù)字的符號位，但是我們并不知道這個數(shù)所代表的位數(shù)b。

unsigned b;  //x代表的位數(shù)
int x;  //擴展此b位數(shù)到r
int r;
int const m = 1U << (b - 1);  //若b是固定的則可以預(yù)先計算出mask

x = x & ((1U << b) - 1);//如果x中的bits在b位置上已經(jīng)是0了，則跳過此步
r = (x ^ m) -m;

上面的代碼需要需要4個操作，但是當(dāng)位寬是恒定的而不是可變時，假設(shè)高位已經(jīng)為0，只需要兩個快速的操作。
不依賴于x位數(shù)在b位置以上為0的方法會稍微快點，但是可移植性比較低：

int const m = CHAR_BIT * sizeof(x) - b;
r = (x << m) >> m;

三步操作從可變位寬中擴展符號

下面的方法在某些機器上可能會比較慢，由于乘法和除法的影響，這個版本需要4步操作。如果你知道b的初始位寬大于1，你可以使用r = (x * multipliers[b]) / multipliers[b]在3個操作中執(zhí)行此類型的符號擴展只需要進行一次數(shù)組查找。

unsigned b;  //代表x的位數(shù)
int x;  //擴展此b位數(shù)到r
#defined M(b) (1U << ((sizeof(x) * CHAR_BIT -B ))  //CHAR_BIT=bits/byte
static int const multipliers[] = 
{
  0,     M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
  M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
  M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
  M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
  M(32)
}; // (如果使用超過64位，則添加更多)
static int const divisors[] = 
{
  1,    ~M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
  M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
  M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
  M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
  M(32)
}; // (為64位添加更多)
#undef M
r = (x * multipliers[b]) / divisors[b];

下面這個版本不可移植，但是在使用算數(shù)右移的架構(gòu)中會更快。

const int s = -b; // 或者:  sizeof(x) * CHAR_BIT - b;
r = (x << s) >> s;

不使用分支來有條件的設(shè)置或者清除位

bool f;  //條件標(biāo)志
unsigned int m;  //位掩碼
unsigned int w;  //需要修改的語句：if (f) w |= m; else w &= ~m; 

w ^= (-f ^ w) & m;

或者，對于超標(biāo)量處理器：

w = (w & ~m) | (-f & m);

不使用分支來獲取一個數(shù)的相反數(shù)

若你想在flag為false時獲取一個相反數(shù)，使用下面的語句來避免使用分支：

bool fDontNegate;  //標(biāo)志位，不獲取v的相反數(shù)
int v;  //要獲取相反數(shù)的值
int r;  //結(jié)果，fDontNegate ? v : -v;

r = (fDontNegate ^ (fDontNegate - 1)) * v;

若你想在flag為true時獲取一個相反數(shù)，可以使用：

bool fNegate;
int v;
int r;

r = (v ^ -fNegate) + fNegate;

通過掩碼來從兩個值中合并位

unsigned int a; //以非掩碼位合并
unsigned int b; //以掩碼位合并
unsigned int mask; //若位來自b，則是1，若從a中來，則是0

統(tǒng)計位設(shè)置（就是計算多少位為1，笨方法）

unsigned int v;  //要統(tǒng)計的數(shù)
unsigned int c;  //結(jié)果
for(c = 0;v; v >>= 1)
{
c += v & 1;
}

通過查表來統(tǒng)計位設(shè)置

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // 要統(tǒng)計的數(shù)
unsigned int c; // 結(jié)果

// 選項 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 

// 選項 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]];


// 以算法生成表:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

統(tǒng)計位設(shè)置，Brian Kernighan的方法

unsigned int v;
unsigned int c;
for (c = 0; v; c++)
{
v &= v - 1;
}

在14,24或32位字中使用使用64位指令對統(tǒng)計位設(shè)置

unsigned int v; 
unsigned int c;

// 最多統(tǒng)計v中的高14位:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// 最多統(tǒng)計v中的高24位:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// 統(tǒng)計32位:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

這種方法需要擁有快速模運算的64位cpu才能更高效，第一種選項只需要3步，第二種要10步，第3種需要15步

并行統(tǒng)計位設(shè)置

unsigned int v; 
unsigned int c; 
static const int S[] = {1, 2, 4, 8, 16};  //Magic Binary Numbers 
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

c = v - ((v >> 1) & B[0]);  //32位
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];

B數(shù)組以二進制形式表示：

B[0] = 0x55555555 = 01010101 01010101 01010101 01010101
B[1] = 0x33333333 = 00110011 00110011 00110011 00110011
B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111
B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111
B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111

我們可以通過Binary Magic Numbers B,S的模式來為較大的整數(shù)調(diào)整此方法。如果存在k位，那么我們需要數(shù)組S和B的元素長度為ceil(lg(k))，并且我們必須計算相同數(shù)量的表達式，因為對于c,S或者B長。對于32位的v，需要16步操作。
統(tǒng)計一個32位整數(shù)v的位數(shù)的最好方法：

v = v - ((v >> 1) & 0x55555555); 
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

統(tǒng)計位數(shù)的最好方法只需要12步操作，與查找表方法相同，但是避免了表的內(nèi)存和潛在的高速緩存未命中。它是上訴存并行方法和先前使用乘法方法的混種（在本節(jié)中用來64位指令來統(tǒng)計位），盡管不使用64位指令。字節(jié)中設(shè)置的位的計數(shù)在并行完成，并且字節(jié)中所設(shè)置的總位數(shù)通過乘以0x1010101與右移24位完成。
注：緩存命中問題wiki上有相關(guān)說明。

將位設(shè)置從最高有效位計數(shù)到給定位置

下面的例子找出rank of bit，將返回最高位下降到低位的過程中被設(shè)置為1的位總數(shù)

uint64_t v;
unsigned int pos;
uint64_t r;  
r = v >> (sizeof(v) * CHAR_BIT - pos);
// Count set bits in parallel.
// r = (r & 0x5555...) + ((r >> 1) & 0x5555...);
r = r - ((r >> 1) & ~0UL/3);
// r = (r & 0x3333...) + ((r >> 2) & 0x3333...);
r = (r & ~0UL/5) + ((r >> 2) & ~0UL/5);
// r = (r & 0x0f0f...) + ((r >> 4) & 0x0f0f...);
r = (r + (r >> 4)) & ~0UL/17;
// r = r % 255;
r = (r * (~0UL/255)) >> ((sizeof(v) - 1) * CHAR_BIT);

計算奇偶性（笨方法）

unsigned int v;    //需要計算奇偶性的數(shù)
bool parity = false;

while (v)
{
  parity = !parity;
  v = v & (v - 1);
}

上面的代碼時間花費為與位設(shè)置的個數(shù)成正相關(guān)

通過查表來計算奇偶性

static const bool ParityTable256[256] = 
{
#   define P2(n) n, n^1, n^1, n
#   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
    P6(0), P6(1), P6(1), P6(0)
};

unsigned char b; 
bool parity = ParityTable256[b];

// 對于32位
unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
bool parity = ParityTable256[v & 0xff];

unsigned char * p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];

使用64位乘法和模數(shù)除法來計算一個byte的奇偶性

unsigned char b; 
bool parity = 
  (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

上面這種方法總共需要4步操作，但是只適用于bytes

用乘法計算word的奇偶性

下面的方法使用乘法計算一個32位的值，只需要8步

    unsigned int v; // 32-bit word
    v ^= v >> 1;
    v ^= v >> 2;
    v = (v & 0x11111111U) * 0x11111111U;
    return (v >> 28) & 1;

對于64位的值，8步操作也足夠了

    unsigned long long v; // 64-bit word
    v ^= v >> 1;
    v ^= v >> 2;
    v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
    return (v >> 60) & 1;

并行計算奇偶性

unsigned int v; 
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

上面這種方法需要9步，適用于32位。對于byte值，可以通過移除"unsigned int v;"語句下面的兩行來使步數(shù)優(yōu)化到5步。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容