[思路]LeetCode Problems- 476. Number Complement

這篇要講的題目是Number Complement,即為"補數"的意思.題目原文如下:

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.題目的ㄧㄠ

---

題目是要求某數二進位翻轉過後的結果是甚麼數字.

這題跟我先前解過的 [思路]LeetCode Problems- 461. Hamming Distance 有些相似,

都要求出十進位轉二進位,

所以一開始我的想法是:

1.十進位轉二進位

2.0跟1互換,1變0,0變1
3.在反求二進位轉十進位的數值

看起來還蠻合理的,但是在開始著手之後,就發覺整個過程變得很複雜....
首先是在於,我在算十進位轉二進位的方法,主要是一開始先創設32位元的0元素陣列(考慮到int變數的位元範圍下),
再用除法除2時,把求得的餘數1或0放進去
例如對5做轉換求到的值,在陣列中被表示成:

00000000000000000000000000000101

在存著二進位值101前面,其實還有29個0在,若在此時針對此答案做01互換的話,那結果就會變成:

11111111111111111111111111111010

結果我只要轉換後的結果010而已,
但其前面初始為0的元素卻會因此受影響,
找不到當中有甚麼thereshold可以定,
而陣列也不能沒有初始化個數,
C也沒有像C++的vector可變動陣列能夠用
所以這種方法嘗試了很久終將不可行

後來在讀C Primer Plus時,書中有個章節叫做 Bit Fiddling(位元運算),發覺其實可以用位元運算子來寫,十分簡潔與好用
C語言可以處裡變數的"位元子bit",
通常這在硬體設備上處理檔案資訊時十分方便,
這也是為何C常用來撰寫裝置驅動或嵌入式的程式,
有指標可以改記憶體位址,又可以做位元運算

C的位元運算子有兩種:
第一種是位元邏輯運算子,
作用於整數型態的資料
而這跟if判別式中看到的 && ! || 不同
這裡指的位元邏輯運算子作用在單一位元上,
這裡簡單地整理一下:

否定運算子 ~ :1變0,0變1
AND運算子 & : 兩個運算元都是1時才會是1,否則皆為0
OR運算子 | :兩個運算元只要其中有1就會是1
互斥OR運算子 ^ : 兩個運算元都是1時變為0,否則皆為1

第二種是位元位移運算子,
它會將位元左右移位
分為兩個運算子:

左移運算子 << : 位元向左邊移位,空出的位置以0補滿,例如:

(10001010) << 2  //對此二進位數向左移動兩個位置
等於
(00101000)

右移運算子 >> : 位元向右邊移位,空出的位置以0補滿,用法類似於左移運算子


有了以上這些運算子,我們就可以利用他們來 "玩" 整數的值,並做出題目的要求.
怎麼做呢?

題目要求對整數的二進位制作01變換
首先我們要瞭解的是,電腦及C程式,本身貯存的方式就是用二進位的方法
其實可以把轉換這一步省略掉,
直接針對變數做位元的運算就好,
舉例來說,我們在編譯器上寫:
int a = 5;
而存在記憶體中的其實早已是:
00000101
故若我們對變數a左移2個位置,
並把值指定給新變數c的話,會寫成:
int c = a<<2;
會得到甚麼結果呢?
在二進制的角度下,對00000101 左移2個位置會是:
00010100
對此值轉換成十進位,結果是:
20
沒錯,當你這樣key進main檔裡並輸出變數c時,得到的就是這個值
因為二進制早已存在於電腦中,

沒有轉換的問題時,思考就比較簡單了些
接著要考慮的,就是要對輸入的變數做甚麼樣子的遮罩(mask)
使其輸出我們想要的值

在此設計的方法如下:
首先,將變數先跟1做AND:

unsigned int mask = ~0;
這裡寫的是0的否定.不能直接寫1,
因為這樣電腦會判斷出的是 00000001
而不是我所需要的 11111111

當變數跟11111111做AND時判斷出有值的時候,則把mask像左移一位,直到AND沒有值的時候

例如變數是5,即為0000101
跟11111111做AND:

00000101
11111111
(有值,mask向左移一位)

00000101
11111110
(有值,mask向左移一位)

00000101
11111100
(有值,mask向左移一位)

00000101
11111000
(沒有值,停住)
做這個的目的在於要挑出此變數的最大位元數在哪,好做之後的邏輯運算

接者再把變數跟mask做否定,再做AND,就可以把最終的值挑出來了~~!
如下所示:

~00000101
跟
~11111000
也就是
11111010
00000111做AND
等同於
00000010
就是題目要求出的補數值

程式碼如下:

unsigned int mask = ~0;//不能用1
       
while (num & mask)
            mask <<= 1;
       
int ans=~mask & ~num;
   
簡單的幾行,卻能把這原本複雜的題目解出來,而這只需要用到邏輯運算子做01的運算