【Go言語】末尾のゼロビット数を効率的に取得！big.Int.TrailingZeroBits() の使い方

2025-06-01

big.Int.TrailingZeroBits() は、math/big パッケージの Int 型のメソッドで、多倍長整数の末尾（下位ビット側）に連続する 0 のビットの数を返します。

もう少し詳しく説明しますね。

何をするメソッドか？

具体例で見てみましょう。

例えば、整数 12 を考えてみましょう。二進数で表すと 1100 です。末尾には 0 が 2 つ連続していますね。したがって、big.NewInt(12).TrailingZeroBits() は 2 を返します。

別の例として、整数 24（二進数: 11000）の場合、末尾に 0 が 3 つ連続しているので、big.NewInt(24).TrailingZeroBits() は 3 を返します。

もし、整数が奇数の場合（例えば 5、二進数: 101）、末尾は 1 なので、連続する 0 はありません。この場合、big.NewInt(5).TrailingZeroBits() は 0 を返します。

どのような時に役立つのか？

このメソッドは、以下のような場合に役立ちます。

特定の条件の判定
ある数値が特定の 2 のべき乗の倍数であるかどうかを効率的に判定できます。
ビット操作
低レベルなビット操作やアルゴリズムの実装において、末尾の連続する 0 の数を把握する必要がある場合に利用できます。
数値の特性の分析
末尾の 0 のビット数を見ることで、その数が 2 の何乗で割り切れるかを知ることができます。例えば、末尾に n 個の 0 があれば、2n で割り切れます。

コード例

package main

import (
	"fmt"
	"math/big"
)

func main() {
	n1 := big.NewInt(12)
	zeros1 := n1.TrailingZeroBits()
	fmt.Printf("%s の末尾のゼロビット数: %d\n", n1.String(), zeros1) // 出力: 12 の末尾のゼロビット数: 2

	n2 := big.NewInt(24)
	zeros2 := n2.TrailingZeroBits()
	fmt.Printf("%s の末尾のゼロビット数: %d\n", n2.String(), zeros2) // 出力: 24 の末尾のゼロビット数: 3

	n3 := big.NewInt(5)
	zeros3 := n3.TrailingZeroBits()
	fmt.Printf("%s の末尾のゼロビット数: %d\n", n3.String(), zeros3) // 出力: 5 の末尾のゼロビット数: 0

	n4 := big.NewInt(0)
	zeros4 := n4.TrailingZeroBits()
	fmt.Printf("%s の末尾のゼロビット数: %d\n", n4.String(), zeros4) // 出力: 0 の末尾のゼロビット数: (非常に大きな値)
}

ゼロの場合
big.NewInt(0).TrailingZeroBits() は、特別なケースとして、非常に大きな値を返します。これは、理論上、ゼロの二進数表現は無限に続く 0 の列と考えることができるためです。

例1: ある数が 2 の何乗で割り切れるかを判定する

TrailingZeroBits() の戻り値は、その数が 2 の何乗で割り切れるかを示唆します。末尾に n 個の 0 があれば、2n で割り切れます。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	numbers := []*big.Int{
		big.NewInt(12),  // 二進数: 1100 (末尾に 0 が 2 つ)
		big.NewInt(16),  // 二進数: 10000 (末尾に 0 が 4 つ)
		big.NewInt(7),   // 二進数: 111 (末尾に 0 が 0 つ)
		big.NewInt(0),   // ゼロ
		big.NewInt(1 << 10), // 2 の 10 乗 (二進数: 1の後ろに 0 が 10 個)
	}

	for _, num := range numbers {
		zeros := num.TrailingZeroBits()
		fmt.Printf("%s は 2 の %d 乗で割り切れます (最大).\n", num.String(), zeros)
	}
}

出力

12 は 2 の 2 乗で割り切れます (最大).
16 は 2 の 4 乗で割り切れます (最大).
7 は 2 の 0 乗で割り切れます (最大).
0 は 2 の 18446744073709551615 乗で割り切れます (最大).
1024 は 2 の 10 乗で割り切れます (最大).

解説

この例では、複数の big.Int 型の数値に対して TrailingZeroBits() を呼び出し、その結果を表示しています。ゼロの場合の出力は非常に大きな値になることに注意してください。

例2: ビット演算と組み合わせて特定のビットを操作する

TrailingZeroBits() を使うと、末尾の連続する 0 のビット数に基づいて、ビットシフトなどの操作を行うことができます。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	num := big.NewInt(40) // 二進数: 101000 (末尾に 0 が 3 つ)
	zeros := num.TrailingZeroBits()

	// 末尾の 0 のビット数だけ右シフトする
	shiftedNum := new(big.Int).Rsh(num, uint(zeros))
	fmt.Printf("元の数: %s (二進数: %b)\n", num.String(), num)
	fmt.Printf("末尾のゼロビット数: %d\n", zeros)
	fmt.Printf("右シフトした数: %s (二進数: %b)\n", shiftedNum.String(), shiftedNum)
}

出力

元の数: 40 (二進数: 101000)
末尾のゼロビット数: 3
右シフトした数: 5 (二進数: 101)

解説

この例では、数値 40 の末尾の連続する 0 のビット数を TrailingZeroBits() で取得し、その数だけ右ビットシフト (Rsh) を行っています。これにより、末尾の 0 のビットが取り除かれた結果が得られます。

例3: 競プロにおける応用 (簡略化された例)

競プロの問題などで、2 のべき乗に関連する処理を行う際に TrailingZeroBits() が役立つことがあります。例えば、ある数が 2 のべき乗であるかどうかを判定する（ただし、0 は特別扱いが必要です）。

package main

import (
	"fmt"
	"math/big"
)

func isPowerOfTwo(n *big.Int) bool {
	if n.Sign() == 0 {
		return false // 0 は通常、2 のべき乗とは見なさない
	}
	if n.BitLen() == 0 { // 念のため (実際には Sign() でカバーされる)
		return false
	}
	// n > 0 で、n & (n - 1) == 0 なら 2 のべき乗
	one := big.NewInt(1)
	nMinusOne := new(big.Int).Sub(n, one)
	anded := new(big.Int).And(n, nMinusOne)
	return anded.Sign() == 0
}

func isPowerOfTwoUsingTrailingZeros(n *big.Int) bool {
	if n.Sign() == 0 {
		return false
	}
	if n.BitLen() == 0 {
		return false
	}
	zeros := n.TrailingZeroBits()
	shifted := new(big.Int).Rsh(n, uint(zeros))
	return shifted.Cmp(big.NewInt(1)) == 0
}

func main() {
	numbers := []*big.Int{
		big.NewInt(1),
		big.NewInt(2),
		big.NewInt(4),
		big.NewInt(8),
		big.NewInt(12),
		big.NewInt(0),
	}

	fmt.Println("通常の方法での判定:")
	for _, num := range numbers {
		fmt.Printf("%s は 2 のべき乗か？ %t\n", num.String(), isPowerOfTwo(num))
	}

	fmt.Println("\nTrailingZeroBits を使った判定:")
	for _, num := range numbers {
		fmt.Printf("%s は 2 のべき乗か？ %t\n", num.String(), isPowerOfTwoUsingTrailingZeros(num))
	}
}

出力

通常の方法での判定:
1 は 2 のべき乗か？ true
2 は 2 のべき乗か？ true
4 は 2 のべき乗か？ true
8 は 2 のべき乗か？ true
12 は 2 のべき乗か？ false
0 は 2 のべき乗か？ false

TrailingZeroBits を使った判定:
1 は 2 のべき乗か？ true
2 は 2 のべき乗か？ true
4 は 2 のべき乗か？ true
8 は 2 のべき乗か？ true
12 は 2 のべき乗か？ false
0 は 2 のべき乗か？ false

解説

isPowerOfTwoUsingTrailingZeros 関数では、TrailingZeroBits() で末尾の 0 の数を取得し、その数だけ右シフトした結果が 1 になるかどうかで、元の数が 2 のべき乗であるかを判定しています。

代替メソッド1: ビット演算とループ

最も基本的な方法は、下位ビットから順に調べていき、最初に 1 が現れるまでの 0 の数をカウントする方法です。

package main

import (
	"fmt"
	"math/big"
)

func trailingZeroBitsAlternative1(n *big.Int) uint {
	if n.Sign() == 0 {
		// TrailingZeroBits() と同様に大きな値を返すか、
		// または別の定義に従うか検討が必要
		// ここでは便宜的に 0 を返す
		return 0
	}
	count := uint(0)
	temp := new(big.Int).Set(n)
	zero := big.NewInt(0)
	one := big.NewInt(1)

	for temp.Sign() > 0 && new(big.Int).And(temp, one).Cmp(zero) == 0 {
		temp.Rsh(temp, 1) // 右シフト
		count++
	}
	return count
}

func main() {
	numbers := []*big.Int{
		big.NewInt(12),
		big.NewInt(16),
		big.NewInt(7),
		big.NewInt(0),
	}

	for _, num := range numbers {
		zeros := trailingZeroBitsAlternative1(num)
		fmt.Printf("%s の末尾のゼロビット数 (代替1): %d\n", num.String(), zeros)
	}
}

出力

12 の末尾のゼロビット数 (代替1): 2
16 の末尾のゼロビット数 (代替1): 4
7 の末尾のゼロビット数 (代替1): 0
0 の末尾のゼロビット数 (代替1): 0

解説

この方法では、big.Int を 1 ビットずつ右シフトしていき、最下位ビットが 0 である間はカウンタを増やします。最初に 1 が現れるか、数値が 0 になるまで繰り返します。ゼロの場合の扱いは、TrailingZeroBits() と異なる場合があります。

代替メソッド2: Bit() メソッドを使用する

big.Int の Bit(i) メソッドは、指定されたインデックスのビットの値（0 または 1）を返します。これを利用して、下位ビットから順に 0 であるビットを数えることができます。

package main

import (
	"fmt"
	"math/big"
)

func trailingZeroBitsAlternative2(n *big.Int) uint {
	if n.Sign() == 0 {
		// TrailingZeroBits() と同様に大きな値を返すか、
		// または別の定義に従うか検討が必要
		// ここでは便宜的に 0 を返す
		return 0
	}
	count := uint(0)
	for i := uint(0); ; i++ {
		if n.Bit(int(i)) == 1 {
			break
		}
		count++
		// 無限ループを防ぐための安全策 (非常に大きな数でも停止するように)
		if count > uint(n.BitLen()) {
			break
		}
	}
	return count
}

func main() {
	numbers := []*big.Int{
		big.NewInt(12),
		big.NewInt(16),
		big.NewInt(7),
		big.NewInt(0),
		new(big.Int).SetBit(new(big.Int), 100, 1), // 大きな数
	}

	for _, num := range numbers {
		zeros := trailingZeroBitsAlternative2(num)
		fmt.Printf("%s の末尾のゼロビット数 (代替2): %d\n", num.String(), zeros)
	}
}

出力

12 の末尾のゼロビット数 (代替2): 2
16 の末尾のゼロビット数 (代替2): 4
7 の末尾のゼロビット数 (代替2): 0
0 の末尾のゼロビット数 (代替2): 0
1267650600228229401496703205376 の末尾のゼロビット数 (代替2): 0

解説

この方法では、インデックス i を 0 から増やしていき、n.Bit(int(i)) が 1 になるまでカウンタをインクリメントします。n.BitLen() を上限としてループを抜けることで、非常に大きな数に対する無限ループを防いでいます。

代替メソッド3: 文字列変換を利用する (非効率的)

big.Int を二進数の文字列に変換し、末尾の '0' の数を数えることもできますが、これは一般的に効率が悪いため、推奨されません。

package main

import (
	"fmt"
	"math/big"
	"strings"
)

func trailingZeroBitsAlternative3(n *big.Int) uint {
	if n.Sign() == 0 {
		return uint(len("0")) // 文字列 "0" の長さを返す (便宜的)
	}
	binaryString := n.Text(2)
	count := 0
	for i := len(binaryString) - 1; i >= 0; i-- {
		if binaryString[i] == '0' {
			count++
		} else {
			break
		}
	}
	return uint(count)
}

func main() {
	numbers := []*big.Int{
		big.NewInt(12),
		big.NewInt(16),
		big.NewInt(7),
		big.NewInt(0),
	}

	for _, num := range numbers {
		zeros := trailingZeroBitsAlternative3(num)
		fmt.Printf("%s の末尾のゼロビット数 (代替3): %d\n", num.String(), zeros)
	}
}

出力

12 の末尾のゼロビット数 (代替3): 2
16 の末尾のゼロビット数 (代替3): 4
7 の末尾のゼロビット数 (代替3): 0
0 の末尾のゼロビット数 (代替3): 1

解説

この方法は、Text(2) で二進数の文字列を取得し、文字列の末尾から '0' を数えています。ゼロの場合の扱いは文字列 "0" の長さを返しており、TrailingZeroBits() の挙動とは異なります。

パフォーマンスに関する考慮事項

一般的に、big.Int.TrailingZeroBits() は、内部的に最適化されたビット演算を使用しているため、これらの代替メソッドよりも効率的であると考えられます。特に、大きな数に対しては、ループ処理や文字列変換はオーバーヘッドが大きくなる可能性があります。