In [1]:
import sys
import math
import random
In [2]:
def count_bits(x):
"""引数に整数xをとり，xをバイナリ化した時の1の数を返す関数"""
# &と>>はビットレベルの整数演算子．
num_bits = 0
# シフトした値が0b000000になるまで，xと0b000001の&の結果を追加する．
# 値としては1しか入り得ないから，xとして与えた値を2進数にした時の1の数のカウンターになっている．
# 上は1バイトで書いたけど，例えば0b11111111なら255で，これは1が8個になる．
# だから，純粋にバイナリにした時の1の数のカウンター．
while x:
num_bits += x & 1
x >>= 1
return num_bits
In [3]:
count_bits(255)
Out[3]:
In [27]:
# ビット演算まとめ
# bit-wise operatorと呼ばれる．
# 0b000101と 0b000001だから0b000001
print("&: ",5 & 1)
# 0b000101と 0b000001だから0b000101
print("|: ",5 | 1)
# 0b000101と 0b000001だから"0"と"1"の組み合わせのところだけ1になるので，0b000100
print("^: ",5 ^ 1)
# 0b0101なら1b1010になる?
print("~: ", ~5)
# 0b000101を右に1つシフトするから0b000010．左に2つシフトすると0b010100だから20．
print(">>: ",5 >> 1)
print("<<: ",5 << 2)
In [26]:
print("sys.maxsize: ", sys.maxsize)
print("float_info: ", sys.float_info)
In [35]:
# randomの確認．
A = [1, 2, 3,4, 5]
print(random.randrange(28))
print(random.randint(8, 16))
print(random.random())
random.shuffle(A) # random.shuffle(A)自体はNoneを返す． リストのsortの時も同じようなことに当たったことがある．
print(A)
print(random.choice(A))
print(random.sample(A, 3))
In [9]:
def brute_force_parity(x):
"""xを引数にとり，そのビットに1が奇数個あれば1を，偶数個あれば0を返す．
この例だと計算量はO(n)になる．末尾の1桁を毎回取り出す，という考え方に基づく．"""
result = 0
while x:
# x & 1は1桁目だけをmaskで取り出すため．
result ^= x & 1
x >>= 1 # x = x >> 1
return result
In [7]:
brute_force_parity(2)
Out[7]:
In [14]:
def focus_on_one(x):
"""今度は，1の数だけ作業を行うプログラムをかく．ここで使うテクニックは，
x & (x -1)がxのもっとも下位の1を反転させたものになることに基づく．
word列に1がkこ含まれているのであれば，計算量はO(k)となる"""
result = 0
while x:
# 今回は，作業を行った回数そのものを記録する．
result ^= 1
x &= x - 1 # x = x & (x-1)
return result
In [16]:
focus_on_one(13) #1101
Out[16]:
In [3]:
def mask_parity(x):
"""
ビット列を分割して計算する方法
"""
MASK_SIZE = 16
BIT_MASK = 0xFFFF #これは全部1かな．
# 次のPRECOMPUTED_PARITYがわからん．
return (PRECOMPUTED_PARITY[x >> ( 3 * MASK_SIZE)] ^ \
PRECOMPUTED_PARITY[x >> ( 2 * MASK_SIZE)] & BIT_MASK ^\
PRECOMPUTED_PARITY[x >> ( 1 * MASK_SIZE)] & BIT_MASK ^ \
PRECOMPUTED_PARITY[x & BIT_MASK])
In [19]:
mask_parity(13)
In [6]:
def best_parity(x):
x ^= x >> 32
x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x>>1
return x & 0x1
In [7]:
best_parity(13)
Out[7]:
In [12]:
def propagate_right(x):
"""一番右の1だけ0にしてxとXORをとってその部分だけ1にした後1を引いて右に1を詰めたものを作ってorをとる．"""
return x & (x - 1) ^ x - 1 | x
In [11]:
print(propagate_right(12)) #15
print(propagate_right(80)) # 95
In [ ]:
def return_mod(x):
"""一番左のビットだけを0にさせればいい．けどわかんない"""
In [26]:
# 3
def reputation(x):
"""1を一つだけ含むならTrue, そうでないならFalseけどわからん"""
print(x)
while x and count <= 2:
count += 1
if count == 1:
return True
else:
return False
In [27]:
print(reputation(16))
print(reputation(0))
print(reputation(19))
In [31]:
# 64bitの整数のiとjをswapするコード
def bit_swap(x, i, j):
"""bitmaskを使う方法は汎用性がある．
しかし，今回は異なる値かどうか確かめて，同じならswapそのものを実施せず，異なるならそれぞれ反転させると考える"""
# indexがわかってるからシフトが使える
if (x >> i) & 1 != (x >> j) & 1:
bit_mask = (1 << i) | (1 << j) # iとjのところだけ1, 残リは0のbitができる．
x ^= bit_mask #ここでXORを使う．iとjは1だから反転させて，残りは0と元の値のXORになるからそのままの値になる．
return x
In [ ]: