iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 10
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 10

【從面試題學邏輯-10】複習一下:關於位元運算(Bitwise Operation)

終於準備進第二階段嘍/images/emoticon/emoticon02.gif

為了避免剛上路而不清楚,在開始之前先稍微提一下位元運算的東西,但請注意在部分程式語言,可能不支援某些運算符號(例如:據個人所知Python似乎沒有內建XOR的運算符號)。

簡單介紹位元運算

我們不是常看到一堆010101來代表電腦系列嗎?而電腦本身就是由一卡車0與1組成的,而我們宣告變數其實也都是一堆0與1,而這堆0與1本身代表的就是二進位的數字。

我們簡單複習一下二進位是什麼

我們一般日常生活用的是十進位:

我們不會在日常生活中看到,有人在個位數上面寫10對吧

所以只要某個位數超過10,就把除以10拿到的數字,進位到下一位數,把餘數放回去。同理,二進位就是超過2,就把除以2拿到的數字進位,把餘數放回去。

而十進位中說的個位數其實是10的0次方,十位數就是1次方,百位數是2次方。10個10的0次方就是10的1次方對吧?

二進位的第一位數就是2的0次方,第二位數就是2的1次方……以此類推。而位元運算就是把數字在二進位的狀態下做處理喔!比如說我要處理「3」這個數字,系統就會用「0011」來做處理(前面一堆0我們都省略,不然會變的勒勒長)。

有哪些運算方式

※由於示範,所以我們皆取四位來表示,免得數字超長影響版面!

NOT(取補數)

就是把所有的0變成1,所有的1變成0

假設輸入的二進位是0011,給他NOT後就會是1100

AND

AND就是把兩個二進位相同位數各自比較,之後產生一個新的二進位。該位元都是1的話,新的二進位在對應的位置也是1,反之則是0。

  • 1 AND 1 → 1
  • 1 AND 0 → 0
  • 0 AND 0 → 0

我們假設輸入的兩個二進位分別是01011100,結果就會得到0100

0101
1100
------
0100

OR

OR也是把兩個二進位相同位數各自比較,再產生新的二進位。只不過只要二個二進位中該位數任一個是1,新二進位的該位數就會是1。

  • 1 AND 1 → 1
  • 1 AND 0 → 1
  • 0 AND 0 → 1

0101
1100
------
1101

XOR

XOR也是把兩個二進位相同位數各自比較,再產生新的二進位。只不過! OR是兩個數的該位數不相同才會給1,相同則是0。

不一樣才會給1啦

  • 1 AND 1 → 0
  • 1 AND 0 → 1
  • 0 AND 0 → 0

0101
1100
------
1001

左移、邏輯右移、數學右移

左移就是把整串二進位往左移動指定的數量

假設0001,左移1位數就是0010

那右移怎麼會分邏輯和數學呢?因為電腦紀錄負數的方式是用2s補數(說明

如果是邏輯右移,就單純和左移一樣往右移動,而數學右移則會在保留正負數的情況下做右移,所以兩個操作出來的結果可能會不同。


複習完了,明天我們就開始解題吧!


上一篇
【從面試題學邏輯-9】如何旋轉矩陣/二維陣列 ?到底是轉魔術方塊還是轉大腦?(CTCI 1.7 旋轉矩陣)
下一篇
【從面試題學邏輯-11】如何在一堆出現兩次的數中找到不重複的那位仁兄?(leetcode 136. Single Number)
系列文
新手也能學!一起從面試題理解程式邏輯!30

1 則留言

0
hk_escapee
iT邦新手 5 級 ‧ 2020-12-28 17:22:53

應該是這樣:
OR
OR也是把兩個二進位相同位數各自比較,再產生新的二進位。只不過只要二個二進位中該位數任一個是1,新二進位的該位數就會是1。

1 AND 1 → 1
1 AND 0 → 1
0 AND 0 → 0

我要留言

立即登入留言