【資料結構與算法】位運算

位運算符

<code>&amp;</code> ：與

<code>|</code> ：或

<code>^</code> ：異或

<code>~</code> ：非（取反）

<code>&gt;&gt;</code> <code>&lt;&lt;</code> ：右移（補符号位），左移（補0）

<code>&gt;&gt;&gt;</code> ：右移（0補充高位）

對于int型，1&lt;&lt;35與1&lt;&lt;3是相同的，而左邊的操作數是long型時需要對右側操作數模64

異或：

可以了解為不進位加法：1+1=0，0+0=0，1+0=1

性質：

1、交換律：a ^ b = b ^ a

2、結合律：(a ^ b) ^ c = a ^ (b ^ c)

3、對于任何數x，都有x ^ x = 0，x ^ 0 = x

4、自反性：a ^ b ^ b = a ^ 0 = a，連續和同一個因子做異或運算，最終結果為自己

應用

<code>x &amp; 1 = 1</code> x是奇數

<code>x &amp; 1 = 0</code> x是偶數

核心是判斷二進制數最後一位是1還是0

使用前提：a，b不相等

<code>(num^(num&gt;&gt;31))+(num&gt;&gt;&gt;31)</code>

11111111 11111111 11111111 11110111：num

11111111 11111111 11111111 11111111：num&gt;&gt;31

00000000 00000000 00000000 00001000：num^(num&gt;&gt;31)

00000000 00000000 00000000 00000001：num&gt;&gt;&gt;31

00000000 00000000 00000000 00001001：num^(num&gt;&gt;31))+(num&gt;&gt;&gt;31

正數顯然滿足

負數的相反數是原碼含符号位取反加一

<code>x&amp;(x-1)</code> ：可以使二進制數x的最低位的1變成0；

例題

1-1000這1000個數放在含有1001個元素的數組中，隻有唯一的一個元素值重複，其它均隻出現一次。每個數組元素隻能通路一次，設計一個算法，将它找出來;不用輔助存儲空間，能否設計一個算法實作?

核心：<code>x^x=0</code>

可以強行配湊消去其他元素：這1001個元素連續異或，再異或上1-1000這1000個數。

其他元素都出現2次，異或後變成0.而唯一的一個元素值出現3次，連續異或後值不變。

一個數組裡除了某一個數字之外，其他的數字都出現了兩次。請寫程式找出這個隻出現一次的數字。

請實作一個函數，輸入一個整數，輸出該整數二進制表示中1的個數。

例：9的二進制表示為1001，有2位是1

法一：

該二進制數不斷無符号右移并與1做與運算，結果為1則count++，直到該數變為0

法二：

每次使該二進制數的一個為1的二進制位變成0，count++，直到該數變成0；

<code>x&amp;(x-1)</code> ：可以使二進制數的最低位的1變成0；

用一條語句判斷一個整數是不是2的整數次方

也就是一個整數的二進制形式中為1的二進制位是不是隻有一個。聯系上一題，也就是count是不是為1

先取出偶數位和奇數位，偶數結果右移一位，奇數結果左移一位，最後異或

abababab abababab abababab abababab

a0a0a0a0 a0a0a0a0 a0a0a0a0 a0a0a0a0（ou）

0b0b0b0b 0b0b0b0b 0b0b0b0b 0b0b0b0b（ji）

0a0a0a0a 0a0a0a0a 0a0a0a0a 0a0a0a0a（ou&gt;&gt;&gt;1）

b0b0b0b0 b0b0b0b0 b0b0b0b0 b0b0b0b0（ji&lt;&lt;1)

babababa babababa babababa babababa

給定一個介于0和1之間的實數，（如0.625)，類型為double,列印它的二進制表示(0.101，因為小數點後的二進制分别表示0.5,0.25.0.125......) 。

如果該數字無法精确地用32位以内的二進制表示，則列印“ERROR”

數組中隻有一個數出現了1次，其他的數都出現了k次，請輸出隻出現了1次的數。

2個相同的2進制數做不進位加法，結果為0

10個相同的10進制數做不進位加法,結果為O

k個相同的k進制數做不進位加法，結果為0