import sys
import math
import random

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

count_bits(255)

# ビット演算まとめ
# 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)

"""
Explanation: Primitive Types
End of explanation
"""


print("sys.maxsize: ", sys.maxsize)
print("float_info: ", sys.float_info)

"""
Explanation: primitive型について

Python3のintergerは制限なしなので，利用可能なメモリの大きさのintegerを表現可能．
End of explanation
"""


# 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))

"""
Explanation: Primitive typesへのTips

machineに非依存でマスクを作成する方法を知っておくこと．
bitの最低位をclearする早い方法を知っておくこと，あるいはそのindexを取得する方法を知っておくこと．
符号属性とshiftingへの実装を知っておくこと．
Cahceを使うことを考えること．
並列・再配列演算にcommutativityとassociativity(交換性と結合性)が利用可能であることを理解しておくこと．

Notice

bit-wise operatorには慣れておくこと．特にXORは使う．(x ^ 1でxの逆のbitを常に得られる)
numericの計算では特に下記のものを使う．
abs(value)
math.ceil(value): (天井，切り上げ)
math.floor(value): (床，切り捨て)
min(x, y)
max(x, y)
pow(x, y): (x ** y)
math.sqrt(value)


intとstr,floatとstrの変換は把握しておくこと．(str(3.14), float("3.14")
floatはintergerと違い，任意制度演算ではないことを把握しておくこと．
infiniteを表すfloat("inf"), float("-inf")がある．Integerとの比較もできるので，psuedo max-int, psuedo min-intの作成に使われる．
浮動小数点数を比較するときはmath.isclose(a, b, rel_tol=1e-09, abs_tol=0.0)を使うことも考える．rel_tolは相対許容差，abs_tolは最小の絶対許容差．
randomで重要なのは下記のもの．
random.randrange(28): 整数用．random.randrange(stop)あるいはrandom.randrange(start, stop[, step])．
random.randint(8, 16): 整数用．random.randrange(a, b+1)のエイリアス．
random.random(): 浮動小数点([0.0, 1.0))を返す．
random.shuffle(A): 
random.choice(A)
おまけだけど，sampleも使えると思う．
End of explanation
"""


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

brute_force_parity(2)

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

focus_on_one(13) #1101

"""
Explanation: 4.1 Computing the parity of a word
End of explanation
"""


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])

mask_parity(13)

"""
Explanation: 同時に計算することとlookup tableを利用することによる高速化

parityを求めるだけであればbitの順番はどうでもいい．
8bitの11010010の上2桁を求めるなら6つシフトさせて00000011にする次は4つシフト，次は6つシフト，という順番になる．
End of explanation
"""


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

best_parity(13)

"""
Explanation: 4.1の最後

bit列を分割しても良いこととXORを使う．
XORは0, 0と1, 1の組み合わせを0にしてくれるので，今回の目的に非常によくあう．
半分の大きさずつずらして行って，最後の結果を1でmaskして取り出す．
これは，関係のない部分の桁が残ってしまっているため．
End of explanation
"""


def propagate_right(x):
    """一番右の1だけ0にしてxとXORをとってその部分だけ1にした後1を引いて右に1を詰めたものを作ってorをとる．"""
    return x & (x - 1)  ^ x - 1 | x

print(propagate_right(12)) #15
print(propagate_right(80)) # 95

def return_mod(x):
    """一番左のビットだけを0にさせればいい．けどわかんない"""
    

# 3
def reputation(x):
    """1を一つだけ含むならTrue, そうでないならFalseけどわからん"""
    print(x)
    while x and count <= 2:
        count += 1
    if count == 1:
        return True
    else:
        return False

print(reputation(16))
print(reputation(0))
print(reputation(19))

"""
Explanation: 4.1の課題

下記の問題をbitwise operatorを用いてO(1)の計算量で答えよ．
一番右の1から右を全て1にせよ．
x mod a power of 2の計算をせよ．例えば，77 mod 64なら13を返させる．
xが2の累乗の値かどうかをTrue or Falseで返させよ．
End of explanation
"""


# 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

"""
Explanation: 4.2 Swap BITS

x & ( x -1)でxの末尾の1をクリア．
x & ~(x -1 )でで末尾のbitを引き出す?
例えば，16 & ~(16-1) = 16, 11 & ~(11-1) = 1, 20 & ~(20-1) = 4
End of explanation
"""


