目錄

二進制的表示

二進制的位操作

應用： 劍指offer15.統計二進制中1的個數（多種方法，位右移操作、與操作等）

---

轉自：https://www.jianshu.com/p/3a31065a8e58

紅色為自己添加

我們都知道在計算機中所有的信息最終都是以二進制的0和1來表示，而有些算法是通過操作bit位來進行運算的，這就需要我們了解Python中如何去表示二進制，又如何是進行位運算的。

二進制的表示

0b111 類型是整型，一般為二進制32整型或者16整型，常見的是二進制8位整型

bin(n)可以將一個十進制或者其他進制的整型轉化成二進制，返回的類型是字符串表示的二進制整型

n = 0b101
print(type(n))
print(type(bin(n)))

<class 'int'>
<class 'str'>

首先在Python中可以通過以"0b"或者"-0b"開頭的字符串來表示二進制，如下所示

print 0b101 # 輸出5
print 0b10  # 輸出2
print 0b111 # 輸出7
print -0b101 # 輸出-5

由此可知我們用二進制表示的數字在打印之后會變成我們更為熟悉的十進制數，更容易被人理解。
當我們需要看十進制數字的二進制表示時，可以使用bin函數

bin(5)  # 輸出0b101

二進制的位操作

首先一點需要明確的是所有的運算（包括位操作）在計算機內部都是通過補碼形式來進行運算的，關于補碼可以參考文章原碼，反碼和補碼，計算機內部運算示意圖如下：

---

此部分轉自：https://blog.csdn.net/weixin_39671935/article/details/113980497

先簡單說一些概念：

原碼：從符號位開始表示，1是正數，0是負數

反碼：正數的原碼反碼補碼都是一樣的。

負數的反碼是在其原碼的基礎上, 符號位不變，其余各個位取反

比如-5轉成二進制原碼1101，在算出反碼1010

補碼：正數的原碼反碼補碼都是一樣的。

負數的補碼是反碼+1

---

?

?

?

在Python中提供了如下二進制的位操作：

>>  #右移
<<  #左移
|   #位或 
&   #位與
^   #位異或
~   #非

下面我們分別來看下：

左移

0b11 << 2   #輸出為12, 即0b1100
5 << 2      #輸出為20, 即0b10100
-2 << 2     #輸出為-8
5 << 64     #輸出為92233720368547758080L

1. 以0b11為例，0b11的補碼就是0b11，所以左移就是將所有的0和1的位置進行左移，移位之后將空位補0。
2. 負數的左移相對來說就比較復雜，以-2 << 2為例，-2的原碼是10000000000000000000000000000010（32位系統），其補碼為11111111111111111111111111111110，左移之后變為11111111111111111111111111111000，再轉化為原碼即10000000000000000000000000001000，也就是-8，也就是-2*(2**2)=-8
3. 左移超過32位或者64位（根據系統的不同）自動轉化為long類型。
4. 左移操作相當于乘以2**n，以5 << 3為例，相當于5(2*3),結果為40。

右移

0b11 >> 1   #輸出為1, 即0b1
5 >> 1      #輸出為2，即0b10
-8 >> 3     #輸出為-1     

1. 在Python中如果符號位為0，則右移后高位補0，如果符號位為1，則高位補1；
2. 同樣需要先轉化為補碼再進行計算，以-8 >> 3為例，-8的原碼為10...01000,相應的補碼為11...11000,右移后變為1...1,相應的原碼為10...01,即-1。
3. 右移操作相當于除以2**n，8 >> 3相當于8/(2**3)=1

或

0b110 | 0b101   #輸出7,即0b111
-0b001 | 0b101  #輸出-1

同樣是轉化為補碼后再進行或運算, 只要有一位有1就為1。
所以或運算常常用于mask技術中的打開開關，即針對某一位把其置為1
比如將某個數字的第三位置為1，我們可以將mask設置為0b100，然后再或運算

mask = 0b100
0b110000 | mask  #turn on bit 3

與

0b110 & 0b011   #輸出2，即0b010

?與運算常常用于mask技術的關閉開關，即針對某一位把其置為0

mask = 0b10
0b111111 & mask  #turn off bit 2

異或

0b111 ^ 0b111   #輸出0
0b100 ^ 0b111   #輸出3

異或常用于將所有的位反轉

0b1010 ^ 0b1111  #輸出5，即0b0101

?非

~0b101  #輸出2，即0b010
~-3     #輸出2

?非運算就是把0變1，1變0，唯一需要注意的是取非時符號位也會變換，比如-3，原碼是10...011,補碼是11...101,取非后變為00...010,由于符號位為0，所以對應的原碼即為其本身，即2。

?

二進制的減法：

設n=0b1010

則n-1=0b1001

減法原則和十進制的減法一致，只是向前借一的時候，一表示的不是10而是2，加法也是一樣，滿2進1

0	b	1	0	1	0
-	?	?	?	?	1
?	?	?	?	?	=
0	b	1	0	0	1

?

應用： 劍指offer15.統計二進制中1的個數（多種方法，位右移操作、與操作等）

請實現一個函數，輸入一個整數（以二進制串形式），輸出該數二進制表示中 1 的個數。例如，把 9 表示成二進制是 1001，有 2 位是 1。因此，如果輸入 9，則該函數輸出 2。

?

示例 1：

輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'。

示例 2：

輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。

代碼實現：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2021/5/17 17:59
# @Author  : @linlianqin
# @Site    : 
# @File    : 劍指 Offer 15. 二進制中1的個數.py
# @Software: PyCharm
# @description:
'''
請實現一個函數，輸入一個整數（以二進制串形式），輸出該數二進制表示中 1 的個數。
例如，把 9 表示成二進制是 1001，有 2 位是 1。因此，如果輸入 9，則該函數輸出 2。
''''''
思路：將n變成二進制形式，然后計數'1'的個數
'''
class Solution:def hammingWeight(self, n: int) -> int:return bin(n).count('1')# 將其轉化為列表后再諸位變成整數進行相加def hammingWeight1(self,n):return sum(map(int,bin(n)[2:]))n = 0b101
print(Solution().hammingWeight(n))
print(Solution().hammingWeight1(n))# 優化思路，充分利用二進制的位操作
def hammingWeight2(n):# 這里諸位將二進制的數字和1進行運算，若結果為1，則說明當前位置值為1，否則為0count = 0while n: # 當n不全為0時count += n&1 # 這里是進行位與操作,這里的與操作默認是從高位開始的，因此需要進行右移n >>= 1return count
print(hammingWeight2(n))#優化，上述方法進行的是諸位運算，還可以繼續優化，巧妙的利用n&n-1,二進制的減法和十進制一樣，因此能夠檢測出最低位的1，即n-1
# n-1會使得最低位的1及后面的0發生變換，1-0,0-1，然后利用n&n-1來更新n，這樣來達到計數效果
def hammingWeight3(n):count = 0while n:count += 1n &= n-1return count
print(hammingWeight3(n))
print(type(n))
print(type(bin(n)))

2
2
2
2
<class 'int'>
<class 'str'>