ビットごとにブール演算する(ビット毎演算)と3つの基本ブール演算:ぱらぱらめくる『クヌース本4.1』

  • 2進数表記での算術演算にブール演算を使う
    • \mathbf{x} = (x_1,x_2,...,x_k),\mathbf{y}=(y_1,y_2,...,y_k),\mathbf{z}=(z_1,z_2,...,z_k); *_i \in \{0,1\}
  • 非負の整数xをk桁で二進数表記しよう
to_bin.ry <- function(k, x){
  if(k <= 0){
    return(c())
  } else {
    return(append(Recall(k-1, x%/%2), x%%2))
  }
}
to_bin_rev.ry <- function(x){
	sum(x*2^((length(x)-1):0))
}
> (b2134 <- to_bin.ry(20,2134))
 [1] 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0
> to_bin_rev.ry(b2134)
[1] 2134
  • 負の整数は、ビット毎に否定を取り1を末尾ビット加える-\mathbf{x} = (\neg x_1,\neg x_2,...,\neg x_k+1)
negative.ry <- function(x){
	abs(x-1)+c(rep(0,length(x)-1),1)
}
    • ただし、最大数は、全ビットが1の場合になっていて、そこから「反転」する必要があるので、ある値を2進表記して、その負数対応の2進表記を得たら、少し工夫がいる
to_neg_bin_rev.ry <- function(x){
	-sum((rep(1,length(x))-x+c(rep(0,length(x)-1),1))*2^((length(x)-1):0))
} 
(b2134 <- to_bin.ry(20,2134))
(neg.b2134 <- negative.ry(b2134))
to_bin_rev.ry(b2134)
to_bin_rev.ry(neg.b2134)
to_neg_bin_rev.ry(neg.b2134)
> (b2134 <- to_bin.ry(20,2134))
 [1] 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0
> (neg.b2134 <- negative.ry(b2134))
 [1] 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1
> to_bin_rev.ry(b2134)
[1] 2134
> to_bin_rev.ry(neg.b2134)
[1] 1046441
> to_neg_bin_rev.ry(neg.b2134)
[1] -2134
  • \wedge, \vee, \oplusは複数桁で表された値を桁ごとにブール演算してやること(ビット毎演算)について有用な性質を持つ
> boolean.op[,,9]
     [,1] [,2]
[1,]    0    0
[2,]    0    1
> boolean.op[,,15]
     [,1] [,2]
[1,]    0    1
[2,]    1    1
> boolean.op[,,7]
     [,1] [,2]
[1,]    0    1
[2,]    1    0
  • ビット毎演算
    • \mathbf{x} = (x_1,x_2,...,x_k),\mathbf{y}=(y_1,y_2,...,y_k),\mathbf{z}=(z_1,z_2,...,z_k); *_i \in \{0,1\}について次のように定める
    • \mathbf{x} & \mathbf{y} \Longleftrightarrow x_i \wedge y_i = z_i
    • \mathbf{x} | \mathbf{y} \Longleftrightarrow x_i \vee y_i = z_i
    • \mathbf{x} \oplus \mathbf{y} \Longleftrightarrow x_i \oplus y_i = z_i
    • 前の記事で作った、boolean.op()関数をビット毎演算化してみよう
# pはブール演算番号
# p=9は論理積
boolean.op.everybit <- function(x,y,p){
	n <- length(x)
	z <- rep(0,n)
	for(i in 1:n){
		z[i] <- boolean.op[x[i]+1,y[i]+1,p]
	}
	z
}
    • これを使って、0から100の数字に関する2項演算行列を絵にしてみよう

X <- 0:100
k <- 10
p <- 9
M <- matrix(0,length(X),length(X))
for(i in 1:length(X)){
	xi <- to_bin.ry(k,X[i])
	for(j in 1:length(X)){
		xj <- to_bin.ry(k,X[j])
		tmp <- boolean.op.everybit(xi,xj,p)
		M[i,j] <- to_bin_rev.ry(tmp)
	}
}

image(M)

X <- 0:100
k <- 10
p <- 15
M <- matrix(0,length(X),length(X))
for(i in 1:length(X)){
	xi <- to_bin.ry(k,X[i])
	for(j in 1:length(X)){
		xj <- to_bin.ry(k,X[j])
		tmp <- boolean.op.everybit(xi,xj,p)
		M[i,j] <- to_bin_rev.ry(tmp)
	}
}

image(M)
    • 二進数の左や右へのシフトは2の冪の乗算や除算に対応する
      • x << k = \lfloor 2^k x \rfloor: kビット左へシフト
      • x >> k = \lfloor 2^{-k} x \rfloor: kビット右へシフト