iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 14
0
自我挑戰組

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

【從面試題學邏輯-14】你看過灑可可粉,那你看過撒0和1嗎?(CTCI 5.1 在二進位中插入另一個二進位)

題目:
有兩個32位元的數字,分別是N與M,兩個位元位置,分別是i與j。請寫出一個方法,把M插入N的指定位置(i與j),

題目的位元位置是右到左,從0開始算,像陣列那樣

舉例:

N = 11001100
M = 1001
i = 1
j = 4

代表說要像這樣:

11001100
XXX1001X
-----
11010010


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


我們昨天稍微提了Mask的概念,今天我們將實際來練習一下

先帶大家解析一下題目,這個題目是要把一個新的二進位插進原本二進位的指定位置。換句話說,原本的二進位在指定位置的部分就不要了,還記得灑咖啡粉的模具嗎?我們這次就要先依照ij來自製一個模具,把原本二進位不要的地方刪掉,再把新的二進位放進來!

自製Mask

首先我們開一個~0,0的二進位全都是0,所以補數就會讓它全部都是1

再來我們把它往左位移j+1個位元,題目要求的第j位也是要刪掉的,所以我們要多+1才能包含j喔

(我們套用上面的舉例,i=1、j=4來做示範,當然因為32位元太長,這邊一律取後8位做示範,請自行想像前面都是1)

左半部的模具完成了!那右半部怎麼辦呢?

大家是否還記得前兩天提到的2的n次方-1,就會把後面全變成11111這件事?我們可以用這個偷吃步來一次幫我們做好右邊的模具

我們把1往左位移i個位元

接著-1就能把後面全變成1了!

最後我們把兩個模具做OR就可以合起來了

接下來的工作大家都知道了對吧~,先把N和Mask做AND,把指定的位置清空,接著把M往左位移到指定位置。之後把清除過的N和位移過的M做OR,就能把M插進N的指定位置了!

於是我們照著上面的邏輯,可以得到下面這段程式碼:

static int insertBits(int N, int M, int i, int j) {
	int leftMask = ~0 << (j+1);
	int rightMask = (1 << i)-1;
	int mask = leftMask | rightMask;
	return (N & mask) | (M << i);
}

搞定!這個就是運用Mask的其中一個方法喔!/images/emoticon/emoticon07.gif


上一篇
【從面試題學邏輯-13】你以為找次方結束了嗎?並沒有,還有4的n次方!(leetcode 342. Power of Four)
下一篇
【從面試題學邏輯-15】Java Integer.bitCount() 原理,當程式達到極致後……就看不懂了!?
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言