資訊專欄INFORMATION COLUMN
摘要：相信大家都知道二進制數按位運算的規則來看一些簡單的例子單純的二進制位之間的這些運算相當簡單，但對我們實際編程并沒有直接幫助，因為編程過程中需要的經常是數字間的運算，比如。
先來看LeetCode上的Divide Two Integers題目要求：
Divide two integers without using multiplication, division and mod operator.
就是說不用乘法，除法，求模運算來實現兩個整數相除，看起來很簡單，我可以用除數減去被除數，直到除數小于被除數，記錄減法操作的次數即可。假設是計算m/n，那么時間復雜度為O(m/n)。用Python實現后，Time Limit Exceeded。我們考慮有沒有更加優化的算法呢？
如果很難想得到，那就先來回憶下二進制數按位運算的一些知識。
二進制數按位運算計算機里面所有數據都存儲為0，1串，所有的運算歸根到底都轉為二進制數的運算。相信大家都知道二進制數按位運算的規則：
來看一些簡單的例子：
1010 & 1100 = 1000 1010 | 1100 = 1110 1010 ^ 1100 = 0110 1010 << 2 = 101000 1010 >> 2 = 10 ~1010 = 0101
單純的二進制位之間的這些運算相當簡單，但對我們實際編程并沒有直接幫助，因為編程過程中需要的經常是數字間的運算，比如 5*(2^4) 。真的是這樣嗎？接著往下看！
計算機中數字的存儲方式我們都知道計算機中萬物皆為0、1，將萬物變為0、1的過程叫做編碼，這里我們只討論將數字編碼為0、1的過程。
計算機中對數字的表示有三種方式：原碼，反碼，補碼：
原碼表示法在數值前面增加了一位符號位（即最高位為符號位）：正數該位為0，負數該位為1。比如十進制3如果用8個二進制位來表示就是 00000011， -3就是 10000011。
反碼表示方法：正數的反碼是其本身；負數的反碼是在其原碼的基礎上，符號位不變，其余各個位取反。
補碼表示方法：正數的補碼是其本身；負數的補碼是在其原碼的基礎上，符號位不變，其余各位取反，最后+1。 (即在反碼的基礎上+1)
原碼容易被人腦直接識別并用于計算，但是對于計算機來說并不友好。所以在計算機系統中，數值一律用補碼來表示、運算和存儲。使用補碼，可以將符號位和數值域統一處理，將加法和減法統一處理。此外，補碼與原碼相互轉換，其運算過程是相同的，不需要額外的硬件電路。詳細的解釋可以參考原碼, 反碼, 補碼詳解。
數字的按位運算計算機中數字存儲為補碼形式，各個數之間的運算也是對它們的補碼做運算，而且得到的結果也是補碼，如下圖：
各種編程語言都提供了對補碼的二進制位直接進行運算的方法。以Python為例：
>>> 0b1010 & 0b1100 8 #1000 >>> 0b1010 | 0b1100 14 #1110 >>> 0b1010 ^ 0b1100 6 #0110 >>> 0b1010 << 2 40 #101000 >>> 0b1010 >> 2 2 #10 >>> ~0b1010 -11 #10000000 00000000 00000000 00001011 >>> type(0b1010)
上面0b開頭的0、1串表示整型數字，在32位操作系統中，Python中int類型一般占32個二進制位，以最后一個求反運算為例子，1010的補碼為
00000000 00000000 00000000 00001010
求反操作后為：
11111111 11111111 11111111 11110101
即為-11(原碼為：10000000 00000000 00000000 00001011)的補碼。（對一個數的補碼求補碼即可得到該數的原碼）
另辟蹊徑的按位運算那么按位運算在實際編程中可以扮演哪些角色呢？簡單點地，可以用來判斷奇、偶數：num & 0x1，或者對一個數變換符號：~num + 1；復雜點的可以用來交換兩個數，求絕對值等等。
> 不用額外的變量實現兩個數字互換。
def swap(num_1, num_2):
num_1 ^= num_2
num_2 ^= num_1
num_1 ^= num_2
return num_1, num_2
證明很簡單，我們只需要明白異或運算滿足下面規律：
0^a = a;
a^a = 0;
a^b^c = a^c^b;
巧妙運用異或可以高效解決很多問題，比如 找出數組中只出現了一次的數（除了一個數只出現一次外，其他數都是出現兩次），以及它的升級版：數組中只出現1次的兩個數字(百度面試題)。
> 不用判斷語句來實現求絕對值。
def bit_abs(num):
negative = num >> 31
return (num ^ negative) - negative
這里假設程序運行環境中操作系統為32位，int型整數(不考慮整數溢出)用32位存儲，因此可以用 num>>31 取出符號位，后面的部分留給大伙證明。
Leetcode 題目思路回到文章開始提到的題目中，我們對除數減去被除數的過程稍作改進。假設求m/n，我們不一次次的 m-n，而是找到n的一個倍數，使得m-x*n盡可能小，這樣能減少循環減法的次數，進而提高效率。我們知道在按位操作中，n << k相當于 n * 2^k，因此可以用2^k 來找合適的x。
我們需要這樣的一個數字k，它使得n 2^k < m < n 2^(k+1)， 然后用m - n*2^k，得到新的m"。再找相應的k"，做減法，如此循環即可。代碼放在這里。
原文地址
相關閱讀
Pyhon wiki: BitwiseOperators
位操作基礎篇之位操作全面總結
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/37621.html
摘要：檢查設定位操作符還有一些其他有用的位屏蔽應用。請注意，位掩碼中的位將有效地關閉十進制數中的相應位，因為。 原文標題：Interesting use cases for JavaScript bitwise operators原文地址：https://blog.logrocket.com/in... 本文首發于公眾號：符合預期的CoyPan JavaScript提供了幾種運算符，可以對...
摘要：位運算符位運算符與邏輯運算符類似，但是位運算符是對每一位進行計算。上面說到的按位取反加，就可以寫成移位運算符右移與無符號右移相似，是將整數所有的位向右移動位，拋棄個低位。空出來的低位用的最高位值補全。 定點數據再計算機中的表示方法 例如一個整數類型（int)的數據在內存中占用了32位。通俗的講就是在內存中挖了32個坑，每一個坑里可以放一個0或者1. 00000000 11111111 ...
摘要：例如，十進制數，用二進制表示則為。按位操作符操作數字的二進制形式，但是返回值依然是標準的數值。不同為真相同為假二進制按位異或運算從左到右按位非為真，為假對每一項進行非操作，遇真則假，遇假則真。 二進制與十六進制 二進制用 0 1 表示 2= 10十六進制 前綴0x 用0123456789ABCDEF表示 2= 0x2二進制與十六進制的轉換十六進制的每位 等于二進制的四位 十六進制 0x...
摘要：例如注意字符串中的負十六進制數字是一個特殊情況，如果你用解析，結果是不正確的。轉換十六進制數時要小心，如果你不知道要轉換對象的類型，不要使用。字符串轉換為數字的方式總結負十六進制數字符串轉換為數字時。 摘要 ：JavaScript 是一個神奇的語言，字符串轉數字有 5 種方法，各有各的坑法! 原文: Converting Strings to Number in Javascript...
閱讀 2653·2021-10-08 10:04
閱讀 2745·2021-09-06 15:02
閱讀 834·2019-08-30 13:50
閱讀 1562·2019-08-30 13:21
閱讀 2598·2019-08-30 11:15
閱讀 2124·2019-08-29 17:19
閱讀 1591·2019-08-26 13:55
閱讀 1270·2019-08-26 10:15
