BIT

algorithmBITGo2021年4月23日

Signed bitとBITとGoと

目次 * きっかけ * Two’s complement(2の補数) * 累積和 * BIT(binary indexed tree) * 転倒数きっかけ先日友人から下記の結果についての質問がきた。 package main import ( "fmt" ) func main() { const a = ^0 fmt.Println(a) } 皆さんも予想してみてほしい。実行は↓から The Go Playground [https://play.golang.org/p/qpWRExXsJ8E] ^0 はNOTでbit反転なのだが、値はintegerのmax値になることなく `-1` となる。これは、ご存知Signed Integer で全bitが1の場合はTwo’s complement(2の補数)となり `-1`が出力される。そして、Goのconstは数値が右辺に来た場合はSigned Integer Typeとデフォルトで解釈する。では uintのmaxの値をbit反転で取りたい場合はというと package