位運算有什麼奇技淫巧？

01-07

眾所周知的應用：異或篩去出現偶數次的數，樹狀數組……
有哪些讓你印象深刻的位運算技巧？
題主腦海中最先想起來的是，剛學「搜索」時看到的位運算解決八皇后的技巧

更新：

1.技巧一

x (x - 1) 用於消去x最後一位的1 x = 1100 x - 1 = 1011 x (x - 1) = 1000

1.1.應用一 用 O(1) 時間檢測整數 n 是否是 2 的冪次。

http://www.lintcode.com/zh-cn/problem/o1-check-power-of-2/

思路解析：

N如果是2的冪次，則N滿足兩個條件。

1.N &>0

2.N的二進位表示中只有一個1

因為N的二進位表示中只有一個1，所以使用N (N - 1)將N唯一的一個1消去，應該返回0。

1.2.應用二 計算在一個 32 位的整數的二進位表式中有多少個 1。

http://www.lintcode.com/zh-cn/problem/count-1-in-binary/

思路解析：

由x (x - 1)消去x最後一位的1可知。不斷使用 x (x - 1) 消去x最後一位的1，計算總共消去了多少次即可。

1.3.應用三 如果要將整數A轉換為B，需要改變多少個bit位？

http://www.lintcode.com/zh-cn/problem/flip-bits/

解題思路：

這個應用是上面一個應用的拓展。

思考將整數A轉換為B，如果A和B在第i（0&<=i&<32）個位上相等，則不需要改變這個BIT位，如果在第i位上不相等，則需要改變這個BIT位。所以問題轉化為了A和B有多少個BIT位不相同。聯想到位運算有一個異或操作，相同為0，相異為1，所以問題轉變成了計算A異或B之後這個數中1的個數。

2技巧二

使用二進位進行子集枚舉

應用 給定一個含不同整數的集合，返回其所有的子集。

http://www.lintcode.com/zh-cn/problem/subsets/

解題思路：

思路就是使用一個正整數二進位表示的第i位是1還是0，代表集合的第i個數取或者不取。

所以從0到2^n-1總共2^n個整數，正好對應集合的2^n個子集。

S = {1,2,3} N bit Combination 0 000 {} 1 001 {1} 2 010 {2} 3 011 {1,2} 4 100 {3} 5 101 {1,3} 6 110 {2,3} 7 111 {1,2,3}

3技巧三

a ^ b ^ b = a

3.1.應用一 數組中，只有一個數出現一次，剩下都出現兩次，找出出現一次的數

http://www.lintcode.com/en/problem/single-number/

思路解析：

因為只有一個數恰好出現一個，剩下的都出現過兩次，所以只要將所有的數異或起來，就可以得到唯一的那個數。

3.2.應用二 數組中，只有一個數出現一次，剩下都出現三次，找出出現一次的。

http://www.lintcode.com/en/problem/single-number-iii/

解題思路：

因為數是出現三次的，也就是說，對於每一個二進位位，如果只出現一次的數在該二進位位為1，那麼這個二進位位在全部數字中出現次數無法被3整除。

膜3運算只有三種狀態：00,01,10，因此我們可以使用兩個位來表示當前位%3，對於每一位，我們讓Two，One表示當前位的狀態，B表示輸入數字的對應位，Two+和One+表示輸出狀態。

0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 One+ = (One ^ B) (~Two) Two+ = (~One+) (Two ^ B)

3.3.應用三 數組中，只有兩個數出現一次，剩下都出現兩次，找出出現一次的

http://www.lintcode.com/en/problem/single-number-iii/

思路解析：

有了第一題的基本的思路，我們可以將數組分成兩個部分，每個部分里只有一個元素出現一次，其餘元素都出現兩次。那麼使用這種方法就可以找出這兩個元素了。

不妨假設出現一個的兩個元素是x，y，那麼最終所有的元素異或的結果就是res = x^y。並且res！=0，那麼我們可以找出res二進位表示中的某一位是1。對於原來的數組，我們可以根據這個位置是不是1就可以將數組分成兩個部分。x，y在不同的兩個子數組中。而且對於其他成對出現的元素，要麼在x所在的那個數組，要麼在y所在的那個數組。

相關閱讀：

乾貨！史上最強位運算面試題大總結！

歡迎關注我的微信公眾號：ninechapter，定期發布最新演算法面試題和解析

謝一哥邀。

以前搞ACM的時候寫過一篇博客總結類似的奇(tou)技(lan)淫(xie)巧(fa)。於是摘抄幾條ACM向的奇技淫巧～

ACM中常使用二進位數1~n位的0/1狀態來表示一個由1~n組成的集合，也就是第k位為1則代表數k在集合中，於是為了提高效率就有了各種花式枚舉集合的方法：

1) 要求集合中不能有兩個相鄰的元素

if ((mask &>&> 1) mask) continue;

2) 在限定必須不取某些元素的前提下枚舉子集

// mask的第x位為0表示x必須不在子集中(原集合中不含這個元素)：

for (int mask1 = mask; mask1 &>= 0; mask1 = (mask1 - 1) mask)

3) 在限定必須取某些元素的前提下枚舉子集

// mask的第x位為1表示x必須在子集中：

for (int mask1 = mask; mask1 &< (1 &<&< m); mask1 = (mask1 + 1) | mask)

4) 找出二進位中恰好含有 k個1的所有數

for (int mask = 0; mask &< 1 &<&< n; ) {

int tmp = mask -mask;

mask = (mask + tmp) | (((mask ^ (mask + tmp)) &>&> 2) / tmp);

}

另外，強烈推薦題主去看一下Matrix67的《位運算簡介及實用技巧》(一)～(四)。

@李冠一的答案已經提到了。我來貼個鏈接。中學搞OI的時候M67大神真是燈塔一般的存在啊。

位運算簡介及實用技巧（一）：基礎篇

位運算簡介及實用技巧（二）：進階篇(1)

位運算簡介及實用技巧（三）：進階篇(2)

位運算簡介及實用技巧（四）：實戰篇

不過夾一點私貨，我個人不覺得在產品開發中使用位運算是個好主意

以及用C++寫位運算一定要記得左右移的優先順序比加減法都低。

位運算還是要慎重，可讀性又不強。我一直以來的觀點是：代碼效率很重要，程序員的時間也很重要。

比如，你覺得這個交換兩個數的方法很神奇：

a=a^b b=a^b a=a^b

於是你寫了一個這樣的函數：

int swap_nums(int *a, int *b) { *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; }

目前為止，完全沒有問題對吧。神奇的事情發生了：

int main(int argc, char* argv[]) { int a = 1; swap_nums(a, a); printf("%d ", a); return 0; }

用戶可能傳入兩個相同的地址（如果項目龐大，完全有可能出現這樣的情況），交換以後，數字就變成0了。

這是因為，無論a的取值，表達式都成立：a ^ a = 0

所以，用位運算真的要特別小心。如果真的感興趣，可以看看http://graphics.stanford.edu/~seander/bithacks.html

你們可以學習一個：http://www.jjj.de/fxt/fxtbook.pdf

分享一個利用 bitmap 的去重演算法。這個演算法時間複雜度可以達到 O(n)。

轉自：怎樣對10億個數字快速去重？——淺析點陣圖數據結構及其應用

最近有個朋友問我一個演算法題——

給你幾億個 QQ 號，怎樣快速去除重複的 QQ 號？

可以作如下假定：

QQ 號數字範圍從 0 到十億，即 [0, 1000000000)，且最多給你 10 億個 QQ 號，這些 QQ 號放在 1 或多個文本文件中，格式是每行一個 QQ 號。

———————————————————————————————————————————

其實在一年前碰過類似的問題，當時的解決方案： 藉助 hash 演算法思想，把一個大文件哈希分割到多個小文件中，而哈希衝突的數字一定會在同一個小文件中，從而保證了子問題的獨立性，然後就可以單獨對小文件通過快速排序來去重——這樣就通過分而治之解決了幾 G 數據進行內排序的問題。

雖然哈希分割文件是 O(n) 的時間複雜度，但總的效率仍是依從快速排序的時間複雜度 O(logn)。

另外，分而治之有個好處就是藉助子問題的獨立性可以利用多核來做並行處理，甚至做分散式處理。後來小菜在《編程珠璣》中看到了點陣圖這個數據結構可以很方便地處理此類問題，時間複雜度可以達到了 O(n) 那怎麼實現這個數據結構呢？

點陣圖的原理類似我們常用的標記數組 map[]/vis[]，比如map[i] = 1 表示把第 i 個元素標記為 1，按照這種思想來去重是很簡單的。

現在假定 QQ 號數字範圍是 [0, 10億)，則要申請 10 億個 char 元素用來做標記，那麼進程就需要 1G 的運行內存。那如果數字範圍增大到 100 億，一般的計算機可能就吃不消了。

點陣圖數據結構只需要 1/8 的空間， 節省 7/8 的內存是非常可觀的 。因為標記只有 1 和 0 兩個值，所以可以 只用一個比特位來做標記 。

設有 char 類型數 x，1 位元組包括 8 個位，我們可以申請 char bit_map[10億/8+1] 的空間，就足以給範圍在 [0,10億)的數字去重了。

選擇 char 類型 而不是 int 等其它類型是考慮到，C 標準規定任何實現都要保證 char 類型占 1 個位元組。

+1 ，是考慮到 C 整型除法向下取整的特點，比如 100/8 結果為 12，這樣訪問編號 &>=96 的比特位（設從 0 開始編號），就會發生數組越界。

我們知道點陣圖的數據結構就是一個數組，而 點陣圖的操作（演算法） 基本依賴於下面3個元操作

set_bit(char x, int n); //將 x 的第 n 位置1，可以通過 x |= (x &<&< n) 來實現

clr_bit(char x, int n); //將 x 的第 n 位清0，可以通過 x = ~(1 &<&< n) 來實現

get_bit(char x, int n); //取出 x 的第 n 位的值，可以通過 (x &>&> n) 1 來實現

有了上面3個元操作，點陣圖的具體操作就簡單了——

比如，要對數字 int x = 1848105 做標記，就可以調用 set_bit(bit_map[x/8], x%8);

除法看做求「組編號」，x/8 即是以 8 個位為一個小組，分組到編號為 idx = x/8 的 bit_map 元素中，然後在組內偏移 lft = x%8 個比特位。

考慮到這些操作是非常頻繁的，所以把上述三個方法改寫成宏減少函數調用的開銷，並且把 x/8 改為 x&<&<3，x%8改為 x7。

經過上面的分析，寫代碼就很不難了——

/* *CopyRight (C) Zhang Haiba *File: 1billon_remove_duplicate_not_sort.c *Date: 2014.03.11 */ #include & #include & #include & #define MAP_LEN (1000000000/8 + 1) #define BUF_SIZE 10 #define SET_BIT(x, n) ( (x) |= (1 &<&< (n)) ) #define GET_BIT(x, n) ( ((x)&>&>(n)) 1 )


 char bit_map[MAP_LEN];
 int main(int argc, const char *argv[])

 {

     FILE *ifp, *ofp;

     int idx, lft, x;

     char buf[BUF_SIZE]; //cut if number length &> BUF_SIZE ex. range[0, 1000000000) then BUF_SIZE=10

if (argc == 1) { fprintf(stderr, "usage: %s inputfile1 inputfile2 ... ", argv[0]); exit(1); } else { ofp = fopen("./output.txt", "w"); for (idx = 1; idx &<= argc; ++idx) { if ( (ifp = fopen(argv[idx], "r")) == NULL ) { fprintf(stderr, "%s: can not open %s ", argv[0], argv[idx]); exit(1); } printf("processing the %dth file... ", idx); while ( fgets(buf, sizeof buf, ifp) != NULL ) { sscanf(buf, "%d", x); idx = x &>&> 3; lft = x 7; if (GET_BIT(bit_map[idx], lft) == 0) { bit_map[idx] = SET_BIT(bit_map[idx], lft); fprintf(ofp, "%d ", x); } } fclose(ifp); } fclose(ofp); } return 0; }

【測試用例1：】

ZhangHaiba-MacBook-Pro:KandR apple$ time ./a.out input2.txt processing the 1th file...

real 0m0.028s user 0m0.001s sys 0m0.002s

輸入輸出文件對比：

由於實現中故意使用了fgets()，可以防止輸入文本中 長度不合法 的數據

對於長度超過限制，則進行 截斷處理（見上圖左邊第一行） ，同時可以達到濾空的效果。

【測試用例2：】

我們可以寫一個小程序生成N個範圍[0, 10億）的數字，也就是最大的數是包含9個9的999999999。

#include & #include & #include &


#define MAX 1000000000
int main(void)

{

  srand((unsigned)time(NULL));

fprintf(stderr, "this prog output N random numbers to stdout. lease enter the value of N: "); int n, i; scanf("%d", n); for (i = 0; i &< n; ++i) printf("%d ", rand()%MAX); return 0; }

通過這個程序生成 1億個隨機數並重定向輸出到input1.txt，則這個文本文件大概有970Mb ，然後執行測試

ZhangHaiba-MacBook-Pro:KandR apple$ time ./a.out input1.txt processing the 1th file...

real 1m12.263s user 1m0.716s sys 0m2.685s

耗時1分12秒，速度飛快！

如果需要輸出的文本內容是 有序的 ，稍作修改即可——

/* *CopyRight (C) Zhang Haiba *File: 1billon_remove_duplicate_sort.c *Date: 2014.03.11 */


#include &

#include &

#include &

#define MAP_LEN (1000000000/8 +1)

#define BUF_SIZE 10

#define CLR_BIT(x, n) ( (x) = ~(1 &<&< (n)) )
#define SET_BIT(x, n) ( (x) |= (1 &<&< (n)) )
#define GET_BIT(x, n) ( ((x)&>&>(n))  1 )
char bit_map[MAP_LEN];
int main(int argc, const char *argv[])

{

    FILE *fp;

    int idx, lft, x;
    char buf[BUF_SIZE]; //cut if number length &> BUF_SIZE ex. range[0, 1000000000) then BUF_SIZE=10

    if (argc == 1) {

        fprintf(stderr, "usage: %s inputfile1 inputfile2 ...

", argv[0]);

        exit(1);

    } else {

        //memset(bit_map, 0, sizeof bit_mape);

        for (idx = 1; idx &<= argc; ++idx) {
            if ( (fp = fopen(argv[idx], "r")) == NULL ) {
                fprintf(stderr, "%s: can not open %s
", argv[0], argv[idx]);
                exit(1);
            }
            printf("processing the %dth file...
", idx);
            while ( fgets(buf, sizeof buf, fp) != NULL ) {
                sscanf(buf, "%d", x);
                idx = x &>&> 3;

                lft = x  7;

                bit_map[idx] = SET_BIT(bit_map[idx], lft);

            }

            fclose(fp);

        }

fp = fopen("./output.txt", "w"); printf("output to file: output.txt... "); for (idx = 0; idx &< MAP_LEN; ++idx) { for (lft = 0; lft &< 8; ++lft) if (GET_BIT(bit_map[idx], lft) == 1) fprintf(fp, "%d ", (idx&<&<3)+lft); } fclose(fp); } return 0; }

實際測試發現，對於很小的輸入文本（例如空文本），這種方法也需要3~4秒的本機執行時間用於遍歷輸出。

但對於上面將近 1G 的輸入文本文件，測試時間與不排序的實現方案相差無幾，甚至略快一點。

Bit Twiddling Hacks

Lecture 2: Bit Hacks

也不算奇淫技巧，可以看一下Linux系統的文件許可權的實現方式，就是採用了位運算。

一個基於移位和XOR運算的隨機數發生器，周期2^32-1（可以遍歷到除了0外的所有32bit值）：

class RandomNumberGenerator { public: RandomNumberGenerator(uint32_t seed) { next = seed != 0 ? seed : 114514; } uint32_t GenRand() { for (int i = 32; i--;) { uint32_t bit = next 1; next = (next &>&> 1) ^ (0 - bit) 0x80200003u; } return next; } private: uint32_t next; };

原理是Linear feedback shift register。

基本都是些基礎，沒啥奇技。

不過回想起剛學樹狀數組是的確是對其如此厲害地利用了二進位的性質所折服。

還有狀壓的時候也需要用位運算。

所有的技巧，斯坦福計算機系都整理好了 Bit Twiddling Hacks

Hacker"s Delight by Henry S. Warren

Hacker"s Delight (豆瓣)

CRC-16/MODBUS x16+x15+x2+1

輸入不帶校驗碼的數據,輸出 16位校驗碼

輸入帶校驗碼的數據,輸出校驗結果 0(成功) ,1(失敗)

uint16_t crc16_modbus(uint8_t *data,uint16_t length) { uint16_t i,j; uint16_t crc =0xffff; for(j=0; j&&>1)^0xA001:crc&>&>1; } return crc; }

分享一個iOS視圖中的位運算相關的例子：

UIView中有一個autoresizingMask的屬性，它對應的是一個枚舉的值，代碼如下：

typedef NS_OPTIONS(NSUInteger, UIViewAutoresizing) { UIViewAutoresizingNone = 0, UIViewAutoresizingFlexibleLeftMargin = 1 &<&< 0, UIViewAutoresizingFlexibleWidth = 1 &<&< 1, UIViewAutoresizingFlexibleRightMargin = 1 &<&< 2, UIViewAutoresizingFlexibleTopMargin = 1 &<&< 3, UIViewAutoresizingFlexibleHeight = 1 &<&< 4, UIViewAutoresizingFlexibleBottomMargin = 1 &<&< 5 };

這個枚舉類型用來表示某個視圖應該如何在水平或者垂直方向上來調整大小(相對於父視圖)。

每個選項均可啟用或禁用，比如 UIViewAutoresizingFlexibleWidth | UIViewAutoresizingFlexibleHeight 用或操作即可組合多個選項，用與操作即可判斷某個選項是否開啟。比如

enum UIViewAutoresizing resize = UIViewAutoresizingFlexibleWidth | UIViewAutoresizingFlexibleHeight;

resize UIViewAutoresizingFlexibleWidth

即可判斷後者是否開啟。

在UIKit 類似的例子還有很多，比如 UIInterfaceOrientation 可以用 | 來組合以表達App支持的屏幕旋轉方向類型。

a:=a xor b;

b:=a xor b;

a:=a xor b;

不用中間變數交換兩個數的演算法。

高中學noip的時候學的，語言還是pascal。

答完發現M67的文章里有，當年就是這裡學來的，都快忘了我還看過這文章呢23333

我這種蒟蒻看到用位運算實現狀態壓縮DP的時候完全是震驚的...

zkw線段樹算嗎？

dp狀態壓縮算嗎。。

hacker"s delight裡面很多吧

ucos裡面優先順序查找用了位運算

CSAPP Lab1 Data lab