Signed bitとBITとGoと
目次
- きっかけ
- Two’s complement(2の補数)
- 累積和
- BIT(binary indexed tree)
- 転倒数
きっかけ
先日友人から下記の結果についての質問がきた。
package main
import (
"fmt"
)
func main() {
const a = ^0
fmt.Println(a)
}
皆さんも予想してみてほしい。
実行は↓から
^0 はNOTでbit反転なのだが、値はintegerのmax値になることなく
`-1` となる。
これは、ご存知Signed Integer で全bitが1の場合はTwo’s complement(2の補数)となり `-1`が出力される。
そして、Goのconstは数値が右辺に来た場合はSigned Integer Typeとデフォルトで解釈する。
では uintのmaxの値をbit反転で取りたい場合はというと
package main
import (
"fmt"
)
func main() {
const a = ^uint(0)
fmt.Println(a)
}
こんな感じで、uint(0)として、bitの幅をuintのbit数としてしてあげると良い。
そうするとその数のbitが反転し、uintのmax値を取得することができる。
Two’s complement(2の補数)を軽く復習
Signed Integerでのマイナス表現はbitを反転させて1を足す。
- 12をSigned 8bit Integer で表現すると 0000 1100となる。
- -12の場合はbit反転して1を足すことにより 1111 0100 となる。
また、-12から12を得るためににも同様に反転させてから1を足す。
Most Signicant Bit (最上位bit)が0の場合は正の数、0の場合は負の数となる。
応用
least-significant 1 bit
Two’s complementを応用すると、1となっている最下位のbitを取得することができる
a := 12
fmt.Println(a&-a) // 12&-12
0000 1100 & 1111 0100 となり
結果は 0000 0100 // 3となる
BIT(binary Indexed Tree)
累積和
vs:=[1,2,4,6,1,4,6,9]
みたいな数値があった際に、
S0 = 0
S1 = S0 + v0
S2 = S1 + v1...
としておくことにより、
各、区間の和の取得に定数時間 O(1)
値の更新に O(N)かかるデータ構造を作成できる。
例えば、[v2,v5 )
の和を計算する際は S5-S2とすればすぐ求まる。
BIT
これの発展形にBIT(binary indexed tree)がある
これは、区間の和の取得にO(log_N)
値の更新にO(log_N)で行われる
これの仕組みに `累積和`と `Two’s complement`が使われている。
262588213843476
package main
import "fmt"
type BIT struct {
n int
bit []int
}
func (b *BIT) Sum(a int) int {
s := 0
for i := a; i > 0; i -= (i & -i) {
s += b.bit[i]
}
return s
}
func (b *BIT) Add(a, x int) {
for i := a; i < b.n; i += (i & -i) {
b.bit[i] += x
}
}
func (b *BIT) Debug() {
for _, v := range b.bit {
fmt.Print(v)
fmt.Print(" ")
}
fmt.Println()
}
func NewBIT(n int) *BIT {
return &BIT{n + 1, make([]int, n+1)}
}
func main() {
t := []int{1, 2, 4, 6, 1, 4, 6, 9}
b2 := NewBIT(len(t))
for i, v := range t {
b2.Add(i+1, v)
b2.Debug()
}
fmt.Println(b2.Sum(len(t)))
}
0 1 1 0 1 0 0 0 1
0 1 3 0 3 0 0 0 3
0 1 3 4 7 0 0 0 7
0 1 3 4 13 0 0 0 13
0 1 3 4 13 1 1 0 14
0 1 3 4 13 1 5 0 18
0 1 3 4 13 1 5 6 24
0 1 3 4 13 1 5 6 33
33
転倒数
BITを使えば、バブルソートの交換回数をO(log_N)で求めることができる。
※愚直に計算しようとするとO(N²)かかる
[4, 2, 1, 5, 8, 6, 3, 7]のバブルソートの交換回数を求めている
BITを構築しながら、カウントをしていく
262588213843476
package main
import "fmt"
type BIT struct {
n int
bit []int
}
func (b *BIT) Sum(a int) int {
s := 0
for i := a; i > 0; i -= (i & -i) {
s += b.bit[i]
}
return s
}
func (b *BIT) Add(a, x int) {
for i := a; i < b.n; i += (i & -i) {
b.bit[i] += x
}
}
func (b *BIT) Debug() {
for _, v := range b.bit {
fmt.Print(v)
fmt.Print(" ")
}
fmt.Println()
}
func NewBIT(n int) *BIT {
return &BIT{n + 1, make([]int, n+1)}
}
func main() {
t := []int{4, 2, 1, 5, 8, 6, 3, 7}
b := NewBIT(len(t))
ans:=0
for i, v := range t {
ans += i-b.Sum(v)
b.Add(v, 1)
b.Debug()
}
fmt.Println(ans)
}
0 0 0 0 1 0 0 0 1
0 0 1 0 2 0 0 0 2
0 1 2 0 3 0 0 0 3
0 1 2 0 3 1 1 0 4
0 1 2 0 3 1 1 0 5
0 1 2 0 3 1 2 0 6
0 1 2 1 4 1 2 0 7
0 1 2 1 4 1 2 1 8
9
参考:
drken