如何準(zhǔn)備：

Bit manipulation can be a scary thing to many candidates, but it doesn’t need to be! If you’re shaky on bit manipulation, we recommend doing a couple of arithmetic-like problems to boost your skills Compute the following by hand: 1010 - 0001 1010 + 0110 1100^1010 1010 << 1 1001^1001 1001 & 1100 1010 >> 1 0xFF - 1 0xAB + 0x11 If you’re still uncomfortable, examine very carefully what happens when you do subtraction, addition, etc in base 10 Can you repeat that work in base 2?

很多應(yīng)聘者都很害怕“位操作”的題目，害怕確實(shí)是沒有必要的。如果真的在位操作方面不太擅長的話，建議你還是通過在一些練習(xí)好好準(zhǔn)備。筆算下面的題目：

如果這些題目做的時(shí)候還有困惑的話，那就把我們平時(shí)做10進(jìn)制加減的規(guī)則聯(lián)系到2進(jìn)制上。

NOTE: The Windows Calculator knows how to do lots of operations in binary, including ADD, SUBTRACT, AND and OR. Go to View Programmer to get into binary mode while you practice.

注意：windows自帶的計(jì)算器能完成很多2進(jìn)制下的計(jì)算，加減法，求與求門等。點(diǎn)擊計(jì)算機(jī)的“查看” -> “科學(xué)型”，再按F7就能進(jìn)入二進(jìn)制模式計(jì)算了。

Things to Watch Out For:

注意事項(xiàng)：

? It’s really easy to make mistakes on these problems, so be careful! When you’re writing code, stop and think about what you’re writing every couple of lines - or, better yet, test your code mid-way through! When you’re done, check through your entire code ? If you’re bit shifting, what happens when the digits get shifted off the end? Make sure to think about this case to ensure that you’re handling it correctly And (&): 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1 Or (|): 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1 Xor (^): 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0

*在寫代碼的時(shí)候涉及到位操作一定要小心。邊寫的時(shí)候就要邊想下，最好還能測試下。最后全部寫完以后再測試一次。
*在做移位操作的時(shí)候，特別注意移位超過邊界的時(shí)候如何處理。一定要想清楚然后。

Left Shift:

左位移：

x << y means x shifted y bits to the left If you start shifting and you run out of space, the bits just “drop off” For example: 00011001 << 2 = 01100100 00011001 << 4 = 10010000

x< < 表示將x向左位移y位。移動時(shí)超出的部分直接丟棄。

Right Shift:

右位移：

x >> y means x shifted y bits to the right If you start shifting and you run out of space, the bits just “drop off” the end Example: 00011001 >> 2 = 00000110 00011001 >> 4 = 00000001

x>>y 表示將x向右位移y位。移動時(shí)超出的部分直接丟棄。

5 1 You are given two 32-bit numbers, N and M, and two bit positions, i and j Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j) EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100

5.1 給你兩個(gè)32位整數(shù)N,M，還有表示位置的i和j。實(shí)現(xiàn)方法使得N的i至j位等于M。例如：輸入??N = 10000000000, M = 10101, i = 2, j = 6 輸出 N = 10001010100
5.1解答：
解法很簡單，首先將N的i到j(luò)位清零，然后再將M左移i位，最后將兩數(shù)做或。

5 2 Given a (decimal - e g 3 72) number that is passed in as a string, print the binary rep- resentation If the number can not be represented accurately in binary, print “ERROR”

5.2 以字符串形式傳入一個(gè)十進(jìn)制數(shù)(例如3.72)，輸出它的二進(jìn)制表示形式。如果不能準(zhǔn)確表示則輸出"ERROR"
5.2解答：首先我們思考一下小數(shù)是如何用二進(jìn)制表示的。以n = 0.101 = 1 * (1/2^1) + 0 * (1/2^2) + 1 * (1/2^3)為例。
打印輸出整數(shù)部分是非常簡單和直接的。小數(shù)部分我則采用將n*2，取整數(shù)部分，這就相當(dāng)于“移位”的思想。

如果r>1，那么說明小數(shù)點(diǎn)后第一位為1。一直這樣做，我們就能得到小數(shù)的二進(jìn)制表示方法。

(譯者注:本題作者理解為若32位小數(shù)仍無法表示則認(rèn)為該數(shù)無法用二進(jìn)制準(zhǔn)確表示。更為準(zhǔn)確的是判斷標(biāo)準(zhǔn)為：在轉(zhuǎn)換的任意階段，若小數(shù)部分的最后一個(gè)數(shù)字非5，在該數(shù)無法被二進(jìn)制數(shù)準(zhǔn)確表示。)

5 3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation

5.3 給定一個(gè)整數(shù)，輸出與這整數(shù)在二進(jìn)制表示下有相同個(gè)數(shù)“1",大于n的最小值和小于n的最大值。
5.3解答：
暴力算法：
最簡單的方法就是從n向上/向下例舉，判斷是否有對應(yīng)個(gè)數(shù)的”1“。但是這樣的方法一點(diǎn)技術(shù)含量也沒有。
根據(jù)數(shù)字性質(zhì)：
首先觀察
* 若降一個(gè)”1“變?yōu)椤?“，再另一個(gè)”0“必須變?yōu)?；
* 若將第i位的0變?yōu)榱?，第j為的1變?yōu)榱?，那么數(shù)字大小的變化為2^i - 2^j；
* 若要變大數(shù)字必須讓i大于j。
求大于n的最小值：
* 將n轉(zhuǎn)化為二進(jìn)制，從右往左依次遍歷各位，在經(jīng)過1后，遇到的第一個(gè)0，將其置1。這樣就是個(gè)數(shù)字增大了2^i。例:xxxxx011100 變成 xxxxx111100
* 將i位右邊的1置0，這樣數(shù)字總的變化2^i-2^(i-1)。例：xxxxx111100 變成 xxxxx101100
* 為了讓大于n的最小值，將i-1之后的1都移到最右端。
求小于n的最大值，方法類似：
* 將n轉(zhuǎn)化為二進(jìn)制，從右往左一次遍歷各位，在經(jīng)過0后遇到的第一個(gè)。例如xxxxx100011 變?yōu)?xxxxx000011
* 將i位右邊的0置為1。例如xxxxx000011 變?yōu)?xxxxx010011。
* 為求最大值，將i-1位后的1盡量往左移到。
有了算法，開始著手寫代碼的時(shí)候記得將一些常用的方法放到一個(gè)公共的類中，寫出整潔的代碼。

5 4 Explain what the following code does: ((n & (n-1)) == 0)

5.4 解釋下面表達(dá)式的含義 ((n & (n-1)) == 0)
5.4解答
我們來反向思考這個(gè)問題。
A&B=0是什么意思呢？它表示A和B兩個(gè)數(shù)的二進(jìn)制數(shù)每一位都不相同。那么n & (n-1)=0，說明n和n-1也沒有相同的位。
那n-1又表示什么意義呢？從下面的例子你能看發(fā)現(xiàn)什么呢？

當(dāng)你做減法的時(shí)候，主要看最低位，如果最低位為1，那么最低位直接變0；如果最低位為零，那么向高位借1，再減。從低位開始向高位將0變?yōu)?，直到借位的那一位。那么n和n-1的關(guān)系將會如下例所示：

如果n&(n-1)為0的話，說明例子中的abcde均為0，也就是說n中只有一位為1。也就是說n為2的整數(shù)次冪。

5 5 Write a function to determine the number of bits required to convert integer A to integer B Input: 31, 14 Output: 2

5.5 實(shí)現(xiàn)函數(shù)計(jì)算將整數(shù)從A變成B需要變動幾位。例如 輸入:31,14 輸出 2
5.5解答：
本題的解題關(guān)鍵在于發(fā)現(xiàn)A和B之間有多少位是不同的。那如何判斷A和B那些位不同呢?對XOR!
將獲得A和B不同的部分，統(tǒng)計(jì)出有多少個(gè)1就能判斷需要變動幾位了。

5 6 Write a program to swap odd and even bits in an integer with as few instructions as possible (e g , bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc)

5.6 實(shí)現(xiàn)方法將一個(gè)整數(shù)中的偶數(shù)位和奇數(shù)位交換。(例如：將0位和1位交換，2位和3位交換)
5.6解答:
用10101010(0xAA)這樣的掩碼提取出偶數(shù)位的信息，類似的用0x55提取奇數(shù)位的信息。然后錯(cuò)位求或即可。

5 7 An array A[1 n] contains all the integers from 0 to n except for one number which is missing In this problem, we cannot access an entire integer in A with a single operation The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time Write code to find the missing integer Can you do it in O(n) time?

5.7 一個(gè)數(shù)組A[1，n]能容納n個(gè)數(shù)字，現(xiàn)將0到n這n+1個(gè)數(shù)字，隨機(jī)的放入到數(shù)組中。最后會有一個(gè)數(shù)字沒有進(jìn)入數(shù)組。現(xiàn)在讓你找出這個(gè)數(shù)字。但是有如下的限制，不能直接訪問數(shù)組的整個(gè)元素，只能訪問“A[i]的第j位”。寫出代碼找出該元素。能否將時(shí)間復(fù)雜度控制在O(n)。
5.7解答：
(譯者注：作者這里假設(shè)n為奇數(shù)。)
首先我們將0到n的所有數(shù)字的二進(jìn)制表達(dá)列出來。那么我們可以發(fā)現(xiàn)最低位的，大概是這樣的情況：count(0)>=count(1)。
如果我們從中移除了一個(gè)數(shù)字，會怎么樣呢？

如果移除的數(shù)最低位為0，那么count(1)>=count(0)；如果移除的是1，那么count(0)>count(1)。如果n次訪問每個(gè)數(shù)的最低位，那么用以上的準(zhǔn)則我們就能判斷出沒有進(jìn)入數(shù)組的那個(gè)數(shù)字的最后一位是什么。如果最低位是0的話，那就可以排除最低位為1的元素；如最低位為1，那就可以排除末尾為0的。
那下一步怎么辦呢？看次低位的情況？那么我以n=5，未入數(shù)組的數(shù)字為3。經(jīng)過上一輪的排除后，剩下的數(shù)字如圖所示：

那么現(xiàn)在次低位的情況為0 0 1 0 1 0 ，根據(jù)之前的邏輯我們知道，次低位應(yīng)該是1。那么我們繼續(xù)排除。只保留末尾為11的元素。剩下的就是：

再繼續(xù)看倒數(shù)第三位。同樣方法知道第三位應(yīng)該是0。那么我們確定出了丟失的元素。
根據(jù)以上的方法，確定實(shí)現(xiàn)代碼如下：

那算法的時(shí)間復(fù)雜是多少呢？第一次掃描了N次的最低位，第二次為N/2......以此類推，根據(jù)下式子：

所以我的算法的復(fù)雜度為O(n)。

總結(jié)

以上是生活随笔為你收集整理的【IT笔试面试题整理】位操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。