今天刷到 LeetCode 每日一題 3315題目全稱是“構(gòu)造最小位運(yùn)算數(shù)組 II”。只看名字會(huì)覺得又是一道模擬構(gòu)造題讀完題面才發(fā)現(xiàn)它其實(shí)是給你一堆目標(biāo)值讓你逆推一個(gè)滿足位運(yùn)算公式的最小整數(shù)。核心公式很簡單x | (x 1) nums[i]。如果理解到位運(yùn)算的進(jìn)位這道題能在一分鐘內(nèi)寫出核心代碼如果只會(huì)枚舉碰到II這個(gè)加強(qiáng)版就很容易超時(shí)。下面我從題目還原開始把推導(dǎo)過程、完整代碼和提交時(shí)踩過的坑一起說清楚適合想用位運(yùn)算思維刷數(shù)組構(gòu)造題的朋友直接參考。1. 先把題目讀明白正向的一行公式逆向的一個(gè)數(shù)組1.1 輸入輸出長什么樣題目會(huì)給你一個(gè)整數(shù)數(shù)組nums要求返回等長的數(shù)組ans。對于每一個(gè)位置ians[i]要滿足ans[i] | (ans[i] 1) nums[i]而且這個(gè)ans[i]必須是所有滿足條件的整數(shù)里最小的那個(gè)。如果不存在這樣的整數(shù)就填-1。舉個(gè)例子輸入nums [3, 5, 7, 11]返回[1, 4, 3, 9]。驗(yàn)證一下1 | 2 34 | 5 53 | 4 79 | 10 11。從這里就能看出題目里的“最小”不是隨便寫的比如6 | 7也等于 7但 6 不是最小的答案因?yàn)?3 同樣能滿足。1.2 為什么說這是逆推題正向的x | (x 1)很好算但題目給的是結(jié)果要反推出x。更麻煩的是同一個(gè)結(jié)果可能對應(yīng)好幾個(gè)x。比如x 3、x 5、x 6、x 7代入x | (x 1)結(jié)果都是 7必須額外比較哪個(gè)最小。如果只有一兩個(gè)數(shù)暴力從 0 枚舉到nums[i]也不是不行。但既然題目叫“構(gòu)造最小位運(yùn)算數(shù)組 II”說明它是上一題I的加強(qiáng)版nums[i]的規(guī)模通常會(huì)大到?jīng)]法枚舉。這時(shí)候就需要從二進(jìn)制本身找規(guī)律而不是把每個(gè)數(shù)試一遍。1.3 先看一張小表把 0 到 7 的f(x) x | (x 1)列出來規(guī)律其實(shí)非常明顯xx 的二進(jìn)制f(x)00111321033117410055101761107711115這張表透露了兩件事第一f(x)永遠(yuǎn)都是奇數(shù)所以偶數(shù)目標(biāo)值可以直接判死第二f(x)和x之間往往只差一個(gè)二進(jìn)制位。這兩點(diǎn)就是整個(gè)題解的入口。2. 核心觀察x | (x 1)到底改了什么2.1 從加法的連續(xù)進(jìn)位說起要理解x | (x 1)先看x 1在二進(jìn)制里會(huì)發(fā)生什么。比如x 23二進(jìn)制是10111。加 1 的時(shí)候最低位是 1會(huì)產(chǎn)生進(jìn)位第二位也是 1繼續(xù)進(jìn)位第三位還是 1繼續(xù)進(jìn)位直到第四位原本是 0進(jìn)位到這里變成 1進(jìn)位才停住。所以23 1 24也就是11000。再看23 | 2410111 | 11000 11111。對比x和f(x)的二進(jìn)制最低的四位本來就都是 1OR 之后還是 1原來第一個(gè) 0 的位置在第四位OR 之后變成了 1。換句話說f(x)做的事情就是把x二進(jìn)制里從右往左數(shù)第一個(gè) 0 改成 1。這個(gè)描述非常重要。因?yàn)閤 1會(huì)改變一串低位但 OR 操作把那些原本為 1 的低位又“保留”了下來最后只剩最低的那個(gè) 0 位被真正翻轉(zhuǎn)。2.2 結(jié)論一結(jié)果永遠(yuǎn)是奇數(shù)既然f(x)會(huì)把最低位的那個(gè) 0 變成 1那么結(jié)果的第 0 位一定是 1不管x是奇數(shù)還是偶數(shù)。如果x是奇數(shù)最低位本來就是 1x 1讓最低位變 0OR 之后又變回 1。如果x是偶數(shù)最低位本來是 0x 1讓最低位變 1OR 之后就是 1。所以f(x)不可能是偶數(shù)。拿到一個(gè)nums[i]先看它是不是偶數(shù)是偶數(shù)直接填-1這一步過濾掉了一半的數(shù)據(jù)。2.3 結(jié)論二命中的是同一個(gè) 0更嚴(yán)格地說設(shè)p是x二進(jìn)制里從右往左第一個(gè) 0 的位置那么f(x)和x的區(qū)別就只在第p位其余位完全相同。于是有f(x) x 2^p這是個(gè)很強(qiáng)的等式。正向看一旦確定p結(jié)果就確定了逆向看給定目標(biāo)值Y nums[i]x必須是Y減去某個(gè)2^p得到的數(shù)?，F(xiàn)在的任務(wù)就變成了這個(gè)p到底可以取哪些值3. 反推答案數(shù)目標(biāo)值結(jié)尾連續(xù) 1 的個(gè)數(shù)3.1 目標(biāo)值的連續(xù) 1 后綴決定了所有合法 p假設(shè)目標(biāo)值Y是奇數(shù)它的二進(jìn)制最低位一定是 1。從低位往高位數(shù)連續(xù)出現(xiàn)的 1 的個(gè)數(shù)記作c。例如Y 23二進(jìn)制是10111結(jié)尾有 3 個(gè)連續(xù)的 1所以c 3。Y 11二進(jìn)制是1011c 2。Y 21二進(jìn)制是10101結(jié)尾只有一個(gè) 1所以c 1。之前說過構(gòu)造出來的x Y - 2^p而且x的最低p位必須是 1、第p位必須是 0。這意味著Y從最低位開始的前p 1位都必須是 1所以p只能落在 0 到c - 1這個(gè)范圍內(nèi)。為什么p不能大于等于c因?yàn)槟繕?biāo)值Y的第c位是 0如果清掉更高的一位最低位的 0 依然在第c位x 1的進(jìn)位根本不會(huì)傳到p。換句話說真正決定結(jié)果的是Y結(jié)尾這段連續(xù) 1不是靠上的任意 1。舉個(gè)例子Y 7二進(jìn)制111c 3。合法的p可以取 0、1、2對應(yīng)三個(gè)合法的xp2^px 7 - 2^p驗(yàn)證 f(x)0166 | 7 71255 | 6 72433 | 4 7三個(gè)x都滿足條件但最小的那個(gè)對應(yīng)最大的p。因?yàn)闇p去的2^p越大剩下的數(shù)就越小。3.2 最小答案清掉連續(xù) 1 區(qū)間里最高位的那一位所以解法很明確對奇數(shù)Y找到c Y二進(jìn)制結(jié)尾連續(xù) 1 的個(gè)數(shù)然后讓x Y ^ (1 (c - 1))也就是把Y的倒數(shù)第c位從 1 變成 0。再拿Y 23驗(yàn)證c 31 (c - 1) 423 ^ 4 19。19的二進(jìn)制是1001119 | 20 10011 | 10100 10111 23。而且 19 確實(shí)比另一個(gè)合法答案 21 要小。3.3 用 lowbit 一步拿到 c-1 位問題來了計(jì)算c需要循環(huán)數(shù) 1能不能用位運(yùn)算直接算能。如果Y結(jié)尾有c個(gè)連續(xù)的 1那么Y 1結(jié)尾剛好有c個(gè)連續(xù)的 0并且第c位變成 1。也就是說Y 1的最低位 1 對應(yīng)的權(quán)值是2^c。用 lowbit 公式low (Y 1) -(Y 1)得到的是2^c。而我們想清掉的位是第c - 1位權(quán)值是2^(c - 1)正好是low 1。所以最終答案一行搞定ans Y ^ (low 1)看兩個(gè)例子Y 11Y 1 12low 4low 1 2ans 11 ^ 2 9Y 21Y 1 22low 2low 1 1ans 21 ^ 1 20。3.4 邊界情況Y 1 和全 1Y 1的時(shí)候c 1low 2ans 1 ^ 1 0。0 | 1 1沒問題。如果題面里寫的是“正整數(shù)x”那么 0 不算這種情況需要單獨(dú)返回-1但 LeetCode 這道題按非負(fù)整數(shù)處理答案是 0。Y 7、15、31這類全 1 的數(shù)c等于它的二進(jìn)制位數(shù)答案分別是3、7、15。這個(gè)邊界很容易驗(yàn)證代碼寫對了就能對得上。4. 完整代碼從原理落到提交4.1 先寫一個(gè)最直觀的版本為了保險(xiǎn)可以先寫一個(gè)數(shù)連續(xù) 1 的版本邏輯和推導(dǎo)完全一一對應(yīng)。Pythonfrom typing import List class Solution: def minBitwiseArray(self, nums: List[int]) - List[int]: ans [] for num in nums: if num % 2 0: ans.append(-1) continue # 數(shù) num 二進(jìn)制結(jié)尾連續(xù) 1 的個(gè)數(shù) c 0 while (num c) 1: c 1 # 把從右往左第 c 位權(quán)值 1 (c - 1)清 0 ans.append(num ^ (1 (c - 1))) return ans這個(gè)版本不需要任何奇技淫巧while循環(huán)最多跑 30 次通常已經(jīng)能通過。但它還不是最優(yōu)雅的。4.2 用 lowbit 精簡掉循環(huán)既然c ctz(num 1)那就不需要 while。Python 可以寫成class Solution: def minBitwiseArray(self, nums: List[int]) - List[int]: ans [] for num in nums: if num % 2 0: ans.append(-1) continue low (num 1) -(num 1) # 2 的 c 次方 ans.append(num ^ (low 1)) return ans(num 1) -(num 1)就是 lowbit 的經(jīng)典寫法取的是num 1最低位 1 對應(yīng)的權(quán)值。low 1自動(dòng)等價(jià)于1 (c - 1)代碼短思路也清晰。C 版本class Solution { public: vectorint minBitwiseArray(vectorint nums) { vectorint ans; for (int num : nums) { if (num % 2 0) { ans.push_back(-1); continue; } long long t num 1LL; long long low t -t; ans.push_back(num ^ (int)(low 1)); } return ans; } };Java 版本class Solution { public int[] minBitwiseArray(int[] nums) { int[] ans new int[nums.length]; for (int i 0; i nums.length; i) { int num nums[i]; if ((num 1) 0) { ans[i] -1; } else { long t (long) num 1; long low t -t; ans[i] num ^ (int) (low 1); } } return ans; } }這三個(gè)版本核心邏輯完全一樣差異只在要不要擔(dān)心 int 溢出。用num - (low 1)也能得到同樣的結(jié)果因?yàn)橐宓舻哪且晃灰欢ㄊ?1不過用異或更能體現(xiàn)“只翻轉(zhuǎn)指定位”的位運(yùn)算初衷。4.3 復(fù)雜度分析每個(gè)元素只做常數(shù)次加減、按位與、按位異或所以時(shí)間復(fù)雜度是O(n)?？臻g方面只用了輸出數(shù)組本身額外空間是O(1)。如果使用 while 數(shù)連續(xù) 1也不會(huì)改變復(fù)雜度的量級因?yàn)閚um的二進(jìn)制位數(shù)是有限的最多算 30 或 31 次。5. 我提交時(shí)踩過的坑5.1 把 c 數(shù)成了 0第一次我順手用了__builtin_ctz(num)或者 Python 里的(num -num)結(jié)果對num 11這種奇數(shù)怎么算都不對。原因很簡單ctz是數(shù)尾隨 0不是尾隨 1。奇數(shù)最低位是 1尾隨 0 當(dāng)然是 0。正確做法是數(shù)num 1的尾隨 0也就是ctz(num 1)。從原理上記連續(xù) 1 的個(gè)數(shù)正好等于加一之后連續(xù) 0 的個(gè)數(shù)。5.2 以為答案是 num - 1看到6 | 7 7、10 | 11 11很容易有人直接寫num - 1。對num 11確實(shí)能算出 10但 10 不是最小答案9 才是。問題要求的是“最小”不是“隨便一個(gè)”。所以只要目標(biāo)值結(jié)尾連續(xù) 1 的長度超過 1就必須清掉最靠左的那個(gè) 1而不是最低位那個(gè) 1。5.3 忘了處理 num 1num 1時(shí)循環(huán)版本里c 11 (c - 1) 1答案是 0看起來沒什么特別的。但如果你在代碼里最開始判斷if num 1: return -1反而會(huì)錯(cuò)。要不要特判取決于題面定義的是非負(fù)整數(shù)還是正整數(shù)。我刷到的是非負(fù)整數(shù)所以答案是 0。大家在別的平臺(tái)遇到類似題時(shí)先看題面里有沒有“positive”這個(gè)詞。5.4 int 溢出C 和 Java 里num 1在num INT_MAX時(shí)會(huì)溢出。雖然 LeetCode 的常規(guī)數(shù)據(jù)范圍一般到不了這么極端但寫位運(yùn)算題養(yǎng)成長整型習(xí)慣沒有壞處。C 用1LL * num 1Java 用(long) num 1就能完全避開這種隱性 bug。6. 這道題背后的位運(yùn)算套路值得記下來6.1 lowbit(n 1) 就是“連續(xù) 1 長度”的開關(guān)n的二進(jìn)制結(jié)尾連續(xù) 1 的個(gè)數(shù)可以通過n 1的 lowbit 直接算出權(quán)值。這個(gè)技巧在這題里是核心在其他題里也經(jīng)常出現(xiàn)。比如判斷一個(gè)數(shù)是不是2^k - 1可以看n 1是不是 2 的冪處理區(qū)間連續(xù) 1 的問題也可以用類似思路把問題壓縮到最低位附近。遇到形如x | (x 1)、x (x 1)這種組合我現(xiàn)在的第一反應(yīng)不是展開表達(dá)式而是想“加 1 之后進(jìn)位到哪一位停住”。位運(yùn)算和加減法混在一起時(shí)進(jìn)位過程往往比結(jié)果本身更值得分析。6.2 小表比公式更快的場景這題我一開始也卡了幾分鐘后來把x 0到7的x | (x 1)列了一張表規(guī)律立刻清楚了。刷每日一題卡住的時(shí)候先別急著翻題解花兩分鐘列一張小表把 0 到 15 的結(jié)果寫出來很多位運(yùn)算規(guī)律都是肉眼可見的。這個(gè)習(xí)慣幫我省下過不少看題解的時(shí)間。6.3 如果還想繼續(xù)練想鞏固這道題相關(guān)的位運(yùn)算直覺可以順手把“尾隨 0/1”的計(jì)數(shù)再練一遍ctz、clz、lowbit、n (n - 1)這幾個(gè)操作各有什么作用以及它們和加一減一的關(guān)系。把這幾個(gè)基礎(chǔ)操作混熟之后再看這類“給結(jié)果逆推運(yùn)算”的題就不會(huì)覺得無從下手了。