成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

你不知道的按位運(yùn)算

luoyibu / 1190人閱讀

摘要：相信大家都知道二進(jìn)制數(shù)按位運(yùn)算的規(guī)則來看一些簡單的例子單純的二進(jìn)制位之間的這些運(yùn)算相當(dāng)簡單，但對(duì)我們實(shí)際編程并沒有直接幫助，因?yàn)榫幊踢^程中需要的經(jīng)常是數(shù)字間的運(yùn)算，比如。

先來看LeetCode上的Divide Two Integers題目要求：

Divide two integers without using multiplication, division and mod operator.

就是說不用乘法，除法，求模運(yùn)算來實(shí)現(xiàn)兩個(gè)整數(shù)相除，看起來很簡單，我可以用除數(shù)減去被除數(shù)，直到除數(shù)小于被除數(shù)，記錄減法操作的次數(shù)即可。假設(shè)是計(jì)算m/n，那么時(shí)間復(fù)雜度為O(m/n)。用Python實(shí)現(xiàn)后，Time Limit Exceeded。我們考慮有沒有更加優(yōu)化的算法呢？

如果很難想得到，那就先來回憶下二進(jìn)制數(shù)按位運(yùn)算的一些知識(shí)。

二進(jìn)制數(shù)按位運(yùn)算

計(jì)算機(jī)里面所有數(shù)據(jù)都存儲(chǔ)為0，1串，所有的運(yùn)算歸根到底都轉(zhuǎn)為二進(jìn)制數(shù)的運(yùn)算。相信大家都知道二進(jìn)制數(shù)按位運(yùn)算的規(guī)則：

來看一些簡單的例子：

1010 & 1100 = 1000
1010 | 1100 = 1110
1010 ^ 1100 = 0110
1010 << 2   = 101000
1010 >> 2   = 10
~1010       = 0101

單純的二進(jìn)制位之間的這些運(yùn)算相當(dāng)簡單，但對(duì)我們實(shí)際編程并沒有直接幫助，因?yàn)榫幊踢^程中需要的經(jīng)常是數(shù)字間的運(yùn)算，比如 5*(2^4) 。真的是這樣嗎？接著往下看！

計(jì)算機(jī)中數(shù)字的存儲(chǔ)方式

我們都知道計(jì)算機(jī)中萬物皆為0、1，將萬物變?yōu)?、1的過程叫做編碼，這里我們只討論將數(shù)字編碼為0、1的過程。

計(jì)算機(jī)中對(duì)數(shù)字的表示有三種方式：原碼，反碼，補(bǔ)碼：

原碼表示法在數(shù)值前面增加了一位符號(hào)位（即最高位為符號(hào)位）：正數(shù)該位為0，負(fù)數(shù)該位為1。比如十進(jìn)制3如果用8個(gè)二進(jìn)制位來表示就是 00000011， -3就是 10000011。

反碼表示方法：正數(shù)的反碼是其本身；負(fù)數(shù)的反碼是在其原碼的基礎(chǔ)上，符號(hào)位不變，其余各個(gè)位取反。

補(bǔ)碼表示方法：正數(shù)的補(bǔ)碼是其本身；負(fù)數(shù)的補(bǔ)碼是在其原碼的基礎(chǔ)上，符號(hào)位不變，其余各位取反，最后+1。 (即在反碼的基礎(chǔ)上+1)

原碼容易被人腦直接識(shí)別并用于計(jì)算，但是對(duì)于計(jì)算機(jī)來說并不友好。所以在計(jì)算機(jī)系統(tǒng)中，數(shù)值一律用補(bǔ)碼來表示、運(yùn)算和存儲(chǔ)。使用補(bǔ)碼，可以將符號(hào)位和數(shù)值域統(tǒng)一處理，將加法和減法統(tǒng)一處理。此外，補(bǔ)碼與原碼相互轉(zhuǎn)換，其運(yùn)算過程是相同的，不需要額外的硬件電路。詳細(xì)的解釋可以參考原碼, 反碼, 補(bǔ)碼詳解。

數(shù)字的按位運(yùn)算

計(jì)算機(jī)中數(shù)字存儲(chǔ)為補(bǔ)碼形式，各個(gè)數(shù)之間的運(yùn)算也是對(duì)它們的補(bǔ)碼做運(yùn)算，而且得到的結(jié)果也是補(bǔ)碼，如下圖：

各種編程語言都提供了對(duì)補(bǔ)碼的二進(jìn)制位直接進(jìn)行運(yùn)算的方法。以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串表示整型數(shù)字，在32位操作系統(tǒng)中，Python中int類型一般占32個(gè)二進(jìn)制位，以最后一個(gè)求反運(yùn)算為例子，1010的補(bǔ)碼為

00000000 00000000 00000000 00001010

求反操作后為：

11111111 11111111 11111111 11110101

即為-11(原碼為：10000000 00000000 00000000 00001011)的補(bǔ)碼。（對(duì)一個(gè)數(shù)的補(bǔ)碼求補(bǔ)碼即可得到該數(shù)的原碼）

另辟蹊徑的按位運(yùn)算

那么按位運(yùn)算在實(shí)際編程中可以扮演哪些角色呢？簡單點(diǎn)地，可以用來判斷奇、偶數(shù)：num & 0x1，或者對(duì)一個(gè)數(shù)變換符號(hào)：~num + 1；復(fù)雜點(diǎn)的可以用來交換兩個(gè)數(shù)，求絕對(duì)值等等。

> 不用額外的變量實(shí)現(xiàn)兩個(gè)數(shù)字互換。

def swap(num_1, num_2):
    num_1 ^= num_2
    num_2 ^= num_1
    num_1 ^= num_2
    return num_1, num_2

證明很簡單，我們只需要明白異或運(yùn)算滿足下面規(guī)律：

0^a = a;

a^a = 0;

a^b^c = a^c^b;

巧妙運(yùn)用異或可以高效解決很多問題，比如 找出數(shù)組中只出現(xiàn)了一次的數(shù)（除了一個(gè)數(shù)只出現(xiàn)一次外，其他數(shù)都是出現(xiàn)兩次），以及它的升級(jí)版：數(shù)組中只出現(xiàn)1次的兩個(gè)數(shù)字(百度面試題)。

> 不用判斷語句來實(shí)現(xiàn)求絕對(duì)值。

def bit_abs(num):
    negative = num >> 31
    return (num ^ negative) - negative

這里假設(shè)程序運(yùn)行環(huán)境中操作系統(tǒng)為32位，int型整數(shù)(不考慮整數(shù)溢出)用32位存儲(chǔ)，因此可以用 num>>31 取出符號(hào)位，后面的部分留給大伙證明。

Leetcode 題目思路

回到文章開始提到的題目中，我們對(duì)除數(shù)減去被除數(shù)的過程稍作改進(jìn)。假設(shè)求m/n，我們不一次次的 m-n，而是找到n的一個(gè)倍數(shù)，使得m-x*n盡可能小，這樣能減少循環(huán)減法的次數(shù)，進(jìn)而提高效率。我們知道在按位操作中，n << k相當(dāng)于 n * 2^k，因此可以用2^k 來找合適的x。

我們需要這樣的一個(gè)數(shù)字k，它使得n 2^k < m < n 2^(k+1)， 然后用m - n*2^k，得到新的m"。再找相應(yīng)的k"，做減法，如此循環(huán)即可。代碼放在這里。

原文地址

相關(guān)閱讀
Pyhon wiki: BitwiseOperators
位操作基礎(chǔ)篇之位操作全面總結(jié)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/37621.html

相關(guān)文章

  • js中的按位運(yùn)算

    摘要：中的數(shù)字也是按照的標(biāo)準(zhǔn)存儲(chǔ)的，按位存儲(chǔ)，但是操作符不會(huì)直接去操作位，會(huì)將位數(shù)轉(zhuǎn)換成位整數(shù)操作，完成運(yùn)算后再轉(zhuǎn)換成位，這個(gè)位對(duì)用戶來說是透明的。雖然經(jīng)常寫，但是還是對(duì)一些按位運(yùn)算比較迷茫。 javascript中的數(shù)字也是按照IEEE754的標(biāo)準(zhǔn)存儲(chǔ)的，按64位存儲(chǔ)，但是操作符不會(huì)直接去操作64位，會(huì)將64位數(shù)轉(zhuǎn)換成32位整數(shù)操作，完成運(yùn)算后再轉(zhuǎn)換成64位，這個(gè)64位對(duì)用戶來說是透明的。...

    cnio 評(píng)論0 收藏0

  • 【譯】 JavaScript中按位操作符的有趣應(yīng)用

    摘要：檢查設(shè)定位操作符還有一些其他有用的位屏蔽應(yīng)用。請(qǐng)注意，位掩碼中的位將有效地關(guān)閉十進(jìn)制數(shù)中的相應(yīng)位，因?yàn)椤? 原文標(biāo)題：Interesting use cases for JavaScript bitwise operators原文地址：https://blog.logrocket.com/in... 本文首發(fā)于公眾號(hào)：符合預(yù)期的CoyPan JavaScript提供了幾種運(yùn)算符，可以對(duì)...

    oneasp 評(píng)論0 收藏0

  • java學(xué)習(xí)筆記-位運(yùn)算

    摘要：位運(yùn)算符位運(yùn)算符與邏輯運(yùn)算符類似，但是位運(yùn)算符是對(duì)每一位進(jìn)行計(jì)算。上面說到的按位取反加，就可以寫成移位運(yùn)算符右移與無符號(hào)右移相似，是將整數(shù)所有的位向右移動(dòng)位，拋棄個(gè)低位?？粘鰜淼牡臀挥玫淖罡呶恢笛a(bǔ)全。 定點(diǎn)數(shù)據(jù)再計(jì)算機(jī)中的表示方法 例如一個(gè)整數(shù)類型（int)的數(shù)據(jù)在內(nèi)存中占用了32位。通俗的講就是在內(nèi)存中挖了32個(gè)坑，每一個(gè)坑里可以放一個(gè)0或者1. 00000000 11111111 ...

    galaxy_robot 評(píng)論0 收藏0

  • websocket 二進(jìn)制數(shù)據(jù)傳輸基礎(chǔ)準(zhǔn)備工作

    摘要：例如，十進(jìn)制數(shù)，用二進(jìn)制表示則為。按位操作符操作數(shù)字的二進(jìn)制形式，但是返回值依然是標(biāo)準(zhǔn)的數(shù)值。不同為真相同為假二進(jìn)制按位異或運(yùn)算從左到右按位非為真，為假對(duì)每一項(xiàng)進(jìn)行非操作，遇真則假，遇假則真。 二進(jìn)制與十六進(jìn)制 二進(jìn)制用 0 1 表示 2= 10十六進(jìn)制 前綴0x 用0123456789ABCDEF表示 2= 0x2二進(jìn)制與十六進(jìn)制的轉(zhuǎn)換十六進(jìn)制的每位 等于二進(jìn)制的四位 十六進(jìn)制 0x...

    LeviDing 評(píng)論0 收藏0

  • JavaScript字符串轉(zhuǎn)數(shù)字的5種方法及其陷阱

    摘要：例如注意字符串中的負(fù)十六進(jìn)制數(shù)字是一個(gè)特殊情況，如果你用解析，結(jié)果是不正確的。轉(zhuǎn)換十六進(jìn)制數(shù)時(shí)要小心，如果你不知道要轉(zhuǎn)換對(duì)象的類型，不要使用。字符串轉(zhuǎn)換為數(shù)字的方式總結(jié)負(fù)十六進(jìn)制數(shù)字符串轉(zhuǎn)換為數(shù)字時(shí)。 摘要 ：JavaScript 是一個(gè)神奇的語言，字符串轉(zhuǎn)數(shù)字有 5 種方法，各有各的坑法! 原文: Converting Strings to Number in Javascript...

    shengguo 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<