字节--或与加
字節(jié)–或與加
文章目錄
- 字節(jié)--或與加
- 一、題目描述
- 二、分析
- 三、代碼
一、題目描述
給定 x, k ，求滿足 x + y = x | y 的第 k 小的正整數(shù) y 。 | 是二進(jìn)制的或(or)運(yùn)算，例如 3 | 5 = 7。
比如當(dāng) x=5，k=1時(shí)返回 2，因?yàn)?+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。
- 輸入描述:
- 輸出描述:
二、分析
同樣，別看這道題簡單，如果在本地進(jìn)行暴力枚舉y的值再進(jìn)行編譯肯定是沒問題的，但是在OJ上就不一定了，因?yàn)閗 <= 2,000,000,000;普通解法肯定會(huì)超時(shí)，同樣需要另辟捷徑
- 對(duì)于這道題，沒有什么太大的意義，只是擴(kuò)展思維而已；
- 為了快速找到第k小的正整數(shù)y，我們既然不能暴力枚舉，就只能從公式 x + y = x | y 下手，那么 x + y 和 x | y 有什么相同點(diǎn)和不同點(diǎn)呢？
- x + y = x | y 這里可以推出一個(gè)結(jié)論，如果x & y = 0。也就是說，在二進(jìn)制上看，x取1的地方，y必定不能取1。
- 從最低位考慮，若x與y在某一位上同時(shí)取1，則x + y在該位上為0，x | y在該位上為1，前面說這是最低一位x y同時(shí)取1，也就是說沒有更低位加法的進(jìn)位，所以這里兩個(gè)結(jié)果不相等，出現(xiàn)了矛盾。
例子：
x = 0 0 1 0 1 0
y = 1 1 0 1 1 0
x + y = 1 0 0 0 0 0
x | y = 1 1 1 1 1 0
偏差產(chǎn)生的原因是倒數(shù)第二位，x+y=0 x|y=1 且倒數(shù)第一位加法沒有進(jìn)位
- 結(jié)論：x在二進(jìn)制取1的位上，y不能做出改變，只能取0，因?yàn)槿绻鹸的某一位為1了，y在枚舉 的時(shí)候相同的比特位還為1的話那么就不能滿足x + y == x | y了
- 有了上述結(jié)論，可以進(jìn)一步推出只要在x取0的地方，y可以做出改變
- 例如：
x = 10010010011
y = 00000000(0)00 k = 0
y = 00000000(1)00 k = 1
y = 0000000(1)(0)00 k = 2
y = 0000000(1)(1)00 k = 3
y = 00000(1)0(0)(0)00 k = 4
y = 00000(1)0(0)(1)00 k = 5
…
注意觀察括號(hào)里的數(shù)，為x取0的比特位，而如果把括號(hào)里的數(shù)連起來看，正好等于k。
得出結(jié)論，把k表示成二進(jìn)制數(shù)，填入x取0的比特位，x取1的比特位保持為0，得到y(tǒng)。
- —代碼說明— 思路有了，接著就是代碼，顯然用位操作是最合適的方式。
三、代碼
#include <iostream> #include <string> #include <vector>using namespace std;int main() {long long x, k;cin>>x>>k;long long bitNum = 1;long long ans = 0;while(k){if((x & bitNum) == 0){ans += (bitNum * (k & 1));k >>= 1;}bitNum <<= 1;}cout<<ans<<endl;return 0; }- 循環(huán)的思想是每次取得k的最低一位，填入到低位開始，x中比特位為0的位置上。
- 所以用while來判斷k是否大于0，若是，說明k還未完全填完
- 循環(huán)體內(nèi)，需要找到x當(dāng)前可以填的位置，我們用bitNum來從右往左掃描x的每一位
- (x & bitNum) == 0 說明x該位為0,可以把k的當(dāng)前最后一位填入，用 (k & 1) 取出最后一位，用 ans += (bitNum * (k & 1)) 把k的最后一位填入到當(dāng)前bitNum指向的位置。
- 填完后，k右移一位，去掉已經(jīng)被填過的最后一位，bitNum也向左走一位，避免重復(fù)填入x的某個(gè)位置。
- 若x的某個(gè)位置為1，則跳過該位置，向左走一位并觀察是否可以填入。
- 兩次bitNum向左走一位，合并成一句 bitNum <<= 1;
- 如果上面的結(jié)論：x在二進(jìn)制取1的位上，y不能做出改變，只能取0 不明白，我們再換一種講解方式
轉(zhuǎn)二進(jìn)制
滿足這個(gè)運(yùn)算規(guī)律 x + y == x | y 的二進(jìn)制有：
- 0 + 0 == 0 | 0
- 1 + 0 == 1 | 0
- 1 + 1 != 1 | 1 (只有這個(gè)不滿足)
- 所以 x 和y 各自相對(duì)應(yīng)的二進(jìn)制位不能同時(shí)為 1，換言之， x 中 當(dāng)前位 為 1 時(shí)， 與之對(duì)應(yīng)的 y 那一位 肯定是 0 ，所以x 位為 1 的就確定了，可以去除1
X：
Y：
將 Y 中紅色 的 0 去掉看看，得到一組新數(shù)據(jù)
- 這正是 從 1 2 3 4 5 6 7，由于 y 表是按照 k 從1遞增的順序得到的值。所以你有理由猜想 這組新數(shù)據(jù)正是 k ！
- X Y K 之間 有了這個(gè)關(guān)系，就大膽的編寫代碼去驗(yàn)證吧。
- 總之這就是一個(gè)找規(guī)律的游戲
總結(jié)
