論理演算・ビット演算のその0 #Python

はい。

and・論理積

xとyがともに1のときのみに1を返す。ソースコード中ではx&yの記述になります。なんらかの説明文・問題文などではx･yやx&yの表記をされることもあるらしい。

or・論理和

xとyの少なくともどちらか一方が1なら1を返す。ソースコード中ではx|yの記述になります。なんらかの説明文・問題文などではx+yの表記をされることもあるらしい。

xor・排他的論理和

xとyのどちらか一方だけが1なら1を返す。ソースコード中ではx^yの記述になります。

not・否定

反転してます。ソースコード中では~xの記述になります。

ビット演算.py

x=7 #2進数表記で0111
y=11 #2進数表記で1011

#論理積
x&y  は2進数表記でともに1が立っているのが1桁目と2桁目なので、10進数で3となります。

#論理和
x|y は2進数表記で1桁目から4桁目までいずれか・両方に1が立っているため10進数表記で15となります。

#排他的論理和
x^y は2進数表記でどちらか一方だけが1が立っているのが3･4桁目のため10進数表記で12となります。

#否定
~x はビットが反転して4桁目に1が立って? 10進数では-8 と符号も反転します。

はい、x=7が0111で、y=11が1011で論理和でマスクして1111になって10進数で15という値が出てきてソレはなんのかわかっていなかったし、ビット演算をforループで活用するのにどういう働きをするのか午前中ずっと考えていて多分こういうことだろうという例が浮かびました。

他の問題とかに使うときこういう書き方かな.py

#過去記事で書いたビット演算のforループのテンプレート？
youso = 与えられる要素数(色数やナップサック)
seigen = 選べるのは2色までや重量10以下の制限

max_value= -1
#一番外側はどうやらrange(1<<要素数)で書くっぽい。
for all in range(1<<youso):
#各組み合わせから出てくる重量、価値の初期値を0にする
    sum_weight = 0
    sum_value = 0

#ちょっとわかってない要素数ループ
    for i in range(youso):
#ビットチェックの別方法。 らしい。。。
#ビットが立っている(1)なら使っていると判定して、立っていない(0)なら使っていないと判定かな。。。
        if (all>>i & 1):
#使っていると判定された要素の重量と価値を加算する
            sum_weight += weight[[i]
            sum_value += value[i]
    if sum_weight<=W:
#初回はmax_valueが-1になっているのでsum_valueの値が代入される。
#2回目以降は大きい方の数値がmax_valueに代入されるっぽい。
        max_value = max(max_value,sum_value)
print max_value

とあるところのコンビニで私と那珂ちゃんといバイトの女子高生がいるとしてですね。私も那珂ちゃんも一週間の出勤予定はまだきまっておらずです。
そして論理和でどちらか一方か、もしくは両方が出勤している組合せは何通りあるかを数えます。全組み合わせは私(出勤, 休日) 那珂ちゃん(出勤, 休日)で4通りの組合せを7日間で16384通りでしょうか。

那珂ちゃんとアルバイト.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function
import sys
import io
import re
import math

#### メモリ使用量と動作時間チェック仕込み
from guppy import hpy
import time
start = time.clock()
h = hpy()
#### 仕込みここまで
#ビットが立っているなら出勤、立っていなければ休日。
#私の最大出勤日数というか一週間は7日間しか無い。
i=7
#那珂ちゃんの最大出勤日数(ry
n=7

#私か那珂ちゃんのどちらかか、両方が出勤していたらカウンター
cnt=0

for x in xrange(1<<i):
    for y in xrange(1<<n):
#x|yが127なら条件成立。
        if x|y==127:
            cnt+=1
print (cnt)

#### メモリ使用量と動作時間出力
end = time.clock()
print (h.heap())
print (end - start)

iやnが1ずつ加算されていき、そう例えばnが48の時ってどういう状態なのっていうのが

48という数値の時には右から4,5にビットが立っているということで、そこから火曜日と水曜日が出勤であるという情報が成り立ちます。
0番目から6番目まで全てのビットが立つと127になるのでx|yの論理和の127で条件成立の判定としています。
私と那珂ちゃんのどちらか、もしくは両方が出勤というのは3通りの組合せと7日間で2187通りとなります。

まぁ、なんと申しましょうか。。。参考先さまにちゃんと読めば丁寧に書かれていたのに私の脳が足りておりませんでした。
参考先さま
診断人さんのTopCoder初心者向け総当たり特集
http://d.hatena.ne.jp/shindannin/20111202/1322833089

ビットシフト

左へシフト

x = 1<<7　#xは128となる
上記の場合は1を左へ7回シフトするので2進数表記では10000000となる。

右へシフト

x = 1>>7 #xは0となる
上記の場合は1がドコにも立っていなくなるため(多分)に0となります。
x = 7>>1 #xは3となる
上記の場合は7を、2進数表記で111を右へ1回シフトするので011になり、10進数表記で3となります。

はい。私はずっと違和感あるままなんとなく使っていたこの、1<<要素数のループも7日間という要素で1<<7が
for x in xrange(1<<i):
128回ループを回していますが、始まるのは0から始まっているのでループの最後の値は1111111だったのですね。。

追記メモ正の数であること前提で。。。。

http://codeforces.com/contest/76/problem/D
上記問題からよりビット演算に馴染むために追記メモ

・AとBの2つの数が与えられる。
・A=X+Y(論理演算じゃなくて四則演算の方)
・B=X^Y(論理演算のxor、排他的論理和)

論理演算では大きい方の数の1111…を絶対に超えない。
e.g 142をビット表示にすると先頭に正負の表示ありの'0b10001110'、表示なし'10001110'。

コレが最大の1で埋まった数が'0b11111111'や'11111111'。10進数では255。繰り上がりというものが行われないので全部が1で埋まった数以上には絶対に大きくならない。

四則演算の和とxorの結果が等しくなることはあるがxorのほうが大きくなるケースは存在しない(多分)。。

xorの結果がより大きくなることを期待されるペアはお互いにbitが経ってる箇所が重複しないペア。

e.g. 2進数で111と111の(10進数の7同士)ペアのxorは000になる(よね・・・？)。

最大になるような1が重複しないペアは101と010の(10進数で5と2)ペアは2進数表記で111、10進数表記で7。

ということで1の場所が重複するとxorの結果は繰り上がりがないために四則演算の和の結果より小さい数になる。

xorの結果が(より効率的に？)最大になることを期待される1の場所が重複しないペアでの結果も四則演算の和の結果と等しいので証明されているっぽい。

使い道があるかわからない練習した操作

#例としてn=142
>>> bin(n)
'0b10001110'
>>> bin(n)[2:]
'10001110'
#こんな状態を

#len -1ビットシフトで最大値
>>> (1<<len(bin(n)[2:]))-1
255

#またbinすると全てが1に
>>> bin((1<<len(bin(n)[2:]))-1)
'0b11111111'
>>> bin((1<<len(bin(n)[2:]))-1)[2:]
'11111111'

#xorすると先頭の0が消えているためにずれているように見えるが、
#右から見ると0,1反転
>>> bin(n^255)
'0b1110001'
>>> bin(n^255)[2:]
'1110001'

2013/11/01 22:18 細部修正や那珂ちゃんについてなど加筆など行いました。
2013/11/03 27:50 ビットシフトについて追記を行いました。
2014/03/04 23:16 ちょっとだけ確認したことを追記。活用できそうなトコまでは理解できず。

論理演算・ビット演算のその0