big.Int.Rsh()だけじゃない！Go言語で巨大整数を操作する代替メソッド

簡単に言うと、Rshは "Right Shift" の略です。ビット演算における右シフトと同じ概念を、任意の大きさの整数に適用します。

メソッドのシグネチャ

func (z *Int) Rsh(x *Int, n uint) *Int

• n: シフトするビット数を表すuint型です。
• x: 右シフトされる*Intポインタです。
• z: 結果を格納する*Intポインタです。このメソッドはzを返しますが、通常はz自身がレシーバと同じオブジェクトです。つまり、zは結果を書き込む先のオブジェクトです。

動作

z.Rsh(x, n)は、xをnビット右にシフトした結果をzに設定します。

数学的に言うと、これはxを 2n で割る操作と等価です（ただし、負の数の扱いには注意が必要です）。

具体的な例

1. 正の数の場合
   例えば、x=10 ($2進数で 1010$) を n=1 ビット右シフトすると、101 ($2進数で 5$) になります。 10/21=5

2. 負の数の場合
   big.Intの右シフトは、通常のビット演算における算術右シフト（符号を保持するシフト）と同様に動作します。 例えば、x=−10 ($2の補数表現で ...11110110$) を n=1 ビット右シフトすると、−5 ($2の補数表現で ...11111011)になります。これは、 -10 / 2^1 = -5 $ となります。 つまり、最も上位のビット（符号ビット）が保持され、新しいビットは符号ビットと同じ値で埋められます。

使用例

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// 新しい big.Int オブジェクトを作成
	x := new(big.Int)
	y := new(big.Int)
	result := new(big.Int)

	// x に 100 を設定
	x.SetInt64(100) // 2進数: 01100100

	// x を 2 ビット右シフト (100 / 2^2 = 100 / 4 = 25)
	result.Rsh(x, 2)
	fmt.Printf("100 を 2 ビット右シフト: %s (期待値: 25)\n", result.String()) // 出力: 25

	// x に -100 を設定
	y.SetInt64(-100) // 2進数 (補数表現): ...111001100

	// y を 2 ビット右シフト (-100 / 2^2 = -100 / 4 = -25)
	result.Rsh(y, 2)
	fmt.Printf("-100 を 2 ビット右シフト: %s (期待値: -25)\n", result.String()) // 出力: -25

	// 非常に大きな数を試す
	largeNum := new(big.Int)
	largeNum.SetString("12345678901234567890", 10) // 10進数で設定

	// largeNum を 32 ビット右シフト
	result.Rsh(largeNum, 32)
	fmt.Printf("非常に大きな数を 32 ビット右シフト: %s\n", result.String())
	// 計算結果: 12345678901234567890 / 2^32 = 12345678901234567890 / 4294967296 = 2874797042.87... -> 2874797042 (小数点以下切り捨て)
}

---

レシーバー（z）の初期化忘れ

エラーの原因
big.Intのメソッドは、多くの場合、結果を格納するためのレシーバー（z）が必要です。これをnew(big.Int)などで初期化し忘れると、nilポインタ参照のパニック（panic: runtime error: invalid memory address or nil pointer dereference）が発生します。

例

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(100)
	var result *big.Int // 初期化されていない！

	// ここでパニック！
	result.Rsh(x, 2)
	fmt.Println(result)
}

トラブルシューティング
big.Intを操作する際は、必ずnew(big.Int)またはbig.NewInt()を使ってポインタを初期化してください。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(100)
	result := new(big.Int) // 正しく初期化

	result.Rsh(x, 2)
	fmt.Println(result) // 出力: 25
}

元のオブジェクトの意図しない変更（ポインタの扱いの誤解）

エラーの原因
big.Intのメソッドは、多くの場合レシーバーを返すため、メソッドチェーンのように記述できます。しかし、Rshはz（レシーバー）に結果を書き込み、そのzを返します。もしxとzが同じオブジェクトを指している場合、xの値が変更されてしまうことがあります。

例

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(100)
	fmt.Printf("元の x: %s\n", x.String()) // 元の x: 100

	// x をレシーバーとして Rsh を呼び出す
	x.Rsh(x, 2) // x の値が変更される！

	fmt.Printf("シフト後の x: %s\n", x.String()) // シフト後の x: 25
	// もしここで元の 100 の x を使いたかった場合、意図しない変更となる
}

トラブルシューティング
元の値（この場合x）を変更したくない場合は、結果を格納するための新しいbig.Intオブジェクトを用意してください。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(100)
	fmt.Printf("元の x: %s\n", x.String()) // 元の x: 100

	result := new(big.Int) // 新しいオブジェクトを作成
	result.Rsh(x, 2)       // x の値は変更されない

	fmt.Printf("シフト後の result: %s\n", result.String()) // シフト後の result: 25
	fmt.Printf("変更されていない x: %s\n", x.String())     // 変更されていない x: 100
}

負の数のシフト結果の誤解

エラーの原因
Rshは算術右シフト（arithmetic right shift）を行います。これは、負の数の場合、符号ビットを保持しながらシフトするという意味です。他の言語での論理右シフト（logical right shift）に慣れていると、期待する結果と異なることがあります。

例
−10 ($2進数: ...11110110)を1ビット右シフトすると、-5$ ($2進数: ...11111011$) になります。 もしこれが論理右シフトだと期待していた場合（最上位ビットに0が挿入される）、結果は非常に大きな正の数になってしまいます。

トラブルシューティング
big.Int.Rsh()が算術右シフトであることを理解し、負の数に対する動作を把握しておくことです。Goのbig.Intのドキュメントに明記されています。

シフト量nの型 (uint) の誤解

エラーの原因
シフト量nはuint型です。負の値を渡そうとするとコンパイルエラーになります。また、非常に大きなuint値を渡すと、結果が0になる（またはxが負数の場合は-1になる）ことはありますが、これは意図通りなのでエラーというよりは予期しない結果の可能性があります。

トラブルシューティング
nには非負の整数を渡してください。シフト量が非常に大きい場合、結果は0または-1に収束することを知っておきましょう。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(100)
	result := new(big.Int)

	// 正しいシフト量
	result.Rsh(x, 64) // 非常に大きなシフト量
	fmt.Printf("100 を 64 ビット右シフト: %s\n", result.String()) // 0 になる

	// 負のシフト量はコンパイルエラー
	// result.Rsh(x, -2) // compile error: cannot use -2 (untyped int constant) as uint value in argument to result.Rsh
}

big.Intの他のメソッドとの混同

エラーの原因
big.IntにはRshの他にも、Lsh（左シフト）、And、Or、Xorなど、ビット演算に似たメソッドが多数あります。これらのメソッドを誤って使用すると、期待とは異なる結果が得られます。

トラブルシューティング
使用したい操作が本当に右シフト（除算に相当）であるかを確認し、適切なメソッドを呼び出しているか再確認してください。

---

big.Int.Rsh()の基本的な使い方

まずは基本的な使い方から見ていきましょう。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// 1. big.Int オブジェクトの作成
	//    new(big.Int) でポインタを初期化し、その後 SetString や SetInt64 で値を設定します。
	//    big.NewInt() は、指定された int64 値で初期化された新しい big.Int を返します。
	x := big.NewInt(100) // 100 を持つ big.Int を作成
	result := new(big.Int) // 結果を格納するための big.Int を作成 (nil ではないことを確認)

	fmt.Printf("元の値 (x): %s\n", x.String()) // 元の値 (x): 100

	// 2. Rsh メソッドの呼び出し
	//    result.Rsh(x, n) は、x を n ビット右シフトした結果を result に格納します。
	//    数学的には、x を 2^n で割ることに相当します（ただし、負の数の扱いは異なります）。
	shiftBits := uint(2) // シフトするビット数 (uint 型である必要があります)
	result.Rsh(x, shiftBits)

	fmt.Printf("%s を %d ビット右シフト: %s\n", x.String(), shiftBits, result.String())
	// 出力: 100 を 2 ビット右シフト: 25 (100 / 2^2 = 100 / 4 = 25)

	// 別の例: 負の数
	y := big.NewInt(-100)
	resultNeg := new(big.Int)
	fmt.Printf("\n元の値 (y): %s\n", y.String()) // 元の値 (y): -100

	shiftBitsNeg := uint(2)
	resultNeg.Rsh(y, shiftBitsNeg)
	fmt.Printf("%s を %d ビット右シフト: %s\n", y.String(), shiftBitsNeg, resultNeg.String())
	// 出力: -100 を 2 ビット右シフト: -25 (-100 / 2^2 = -100 / 4 = -25)
	// big.Int の Rsh は算術右シフト（符号を保持）です。
}

応用例：非常に大きな数の除算（2の累乗で割る）

Rshは、2n で割る操作に非常に効率的です。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// 非常に大きな数を文字列から設定
	largeNum := new(big.Int)
	largeNum.SetString("987654321098765432109876543210", 10) // 10進数で設定

	result := new(big.Int)
	fmt.Printf("元の巨大な数: %s\n", largeNum.String())

	// 32ビット右シフト (2^32 で割る)
	// 2^32 = 4,294,967,296
	// この大きな数を 4,294,967,296 で割ります
	shiftAmount := uint(32)
	result.Rsh(largeNum, shiftAmount)

	fmt.Printf("%s を %d ビット右シフト (2^%d で除算): %s\n",
		largeNum.String(), shiftAmount, shiftAmount, result.String())

	// 検算 (参考用):
	// var expected big.Int
	// divisor := new(big.Int).Exp(big.NewInt(2), big.NewInt(int64(shiftAmount)), nil)
	// expected.Div(largeNum, divisor)
	// fmt.Printf("通常の除算による結果: %s\n", expected.String())
}

実行結果の例

元の巨大な数: 987654321098765432109876543210
987654321098765432109876543210 を 32 ビット右シフト (2^32 で除算): 229983984534734685045437812

これは、987654321098765432109876543210/232≈229983984534734685045437812.8... となり、小数点以下が切り捨てられた整数部分が取得されています。

応用例：ハッシュ値の一部抽出

大きなハッシュ値（例：SHA-256）から、特定のビット範囲の値を抽出する際に、RshとAndを組み合わせることがあります。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// 例として、非常に大きなハッシュ値を表現する big.Int
	// 実際のハッシュ値はバイト配列から big.Int に変換されます
	hashValue := new(big.Int)
	// これは単なる例の大きな数字です。実際のハッシュ値ではありません。
	hashValue.SetString("0xabcdef0123456789abcdef0123456789abcdef0123456789abcdef0123456789", 0) // 16進数で設定

	fmt.Printf("元のハッシュ値: %s\n", hashValue.Text(16)) // 16進数で表示

	// ハッシュ値の特定のビット範囲を抽出したいとする
	// 例えば、下位から64ビット目を基準として、その上位16ビットを抽出したい場合

	// まず、抽出したいビット範囲の最下位ビットまで右シフトする
	// 例えば、下位から64ビット目から開始したいので、63ビット右シフト
	shiftedHash := new(big.Int)
	shiftAmount := uint(63) // 下位から64ビット目（0-indexedで63）までを右端にする
	shiftedHash.Rsh(hashValue, shiftAmount)

	fmt.Printf("63ビット右シフト後: %s\n", shiftedHash.Text(16))

	// 次に、抽出したいビット数分のマスクを適用する
	// 上位16ビットを抽出したいので、マスクは 2^16 - 1 = 0xFFFF
	mask := big.NewInt(0xFFFF) // 16ビットすべてが1のマスク

	extractedValue := new(big.Int)
	extractedValue.And(shiftedHash, mask) // ビットAND演算

	fmt.Printf("抽出された値 (16ビット): %s (16進数: %s)\n",
		extractedValue.String(), extractedValue.Text(16))
}

この例では、Rshで不要な下位ビットを捨て、Andで必要な上位ビットのみを抽出しています。

RshとLsh（左シフト）を組み合わせることで、ビットローテーション（循環シフト）を実装することも可能です。ただし、これはbig.Intのサイズが固定でないため、少し複雑になります。通常はbig.Int全体をローテーションするのではなく、特定のビット長に収まる値に対して行います。

package main

import (
	"fmt"
	"math/big"
)

// rotateRight は指定されたビット長 (width) で右ローテーションを行います。
// big.Int は可変長なので、width を指定する必要があります。
func rotateRight(x *big.Int, n, width uint) *big.Int {
	// 結果を格納する新しい big.Int
	result := new(big.Int)

	// x を width ビット長のマスクで切り取る
	// (x & ((1 << width) - 1))
	mask := new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), width), big.NewInt(1))
	xCapped := new(big.Int).And(x, mask)

	// ローテーション量 n を width で割った余りにする (n >= width の場合)
	n %= width

	// シフト後の下位ビット部分 (x >> n)
	lowerBits := new(big.Int).Rsh(xCapped, n)

	// シフト後の上位ビット部分 (x << (width - n)) & mask
	upperBits := new(big.Int).Lsh(xCapped, width-n)
	upperBits.And(upperBits, mask) // width を超えるビットをマスクで切り取る

	// 両方の部分を結合 (OR演算)
	result.Or(lowerBits, upperBits)

	return result
}

func main() {
	val := big.NewInt(100) // 10進数 100 (2進数: 01100100)
	width := uint(8)       // 8ビット幅でローテーション

	fmt.Printf("元の値: %s (2進数: %0*s)\n", val.String(), width, val.Text(2))

	// 2ビット右ローテーション
	rotated := rotateRight(val, 2, width)
	fmt.Printf("2ビット右ローテーション (%dビット幅): %s (2進数: %0*s)\n",
		width, rotated.String(), width, rotated.Text(2))
	// 期待: 01100100 -> 00011001 (100 -> 25 ではない！ 64 + 32 + 16 + 1 = 113)
	// 01100100
	// 00011001 (右2ビットが左に回り込む)

	val2 := big.NewInt(0b10000000) // 128 (2進数: 10000000)
	width2 := uint(8)

	fmt.Printf("\n元の値: %s (2進数: %0*s)\n", val2.String(), width2, val2.Text(2))
	rotated2 := rotateRight(val2, 1, width2)
	fmt.Printf("1ビット右ローテーション (%dビット幅): %s (2進数: %0*s)\n",
		width2, rotated2.String(), width2, rotated2.Text(2))
	// 期待: 10000000 -> 01000000 (128 -> 64)
}

この例では、rotateRight関数がbig.Intの右ローテーションを実装しています。RshとLshを組み合わせて、指定されたビット幅を超えないようにマスクで切り取ることで、ローテーションを実現しています。

---

big.Int.Rsh()は非常に大きな整数を右シフト（2n で割る）するための効率的な方法ですが、状況によっては他のアプローチを検討することもあります。主な代替方法としては、直接的な除算や、より低レベルなバイト配列操作が挙げられます。

big.Int.Div() を使用する（直接的な除算）

Rsh()の主な数学的効果は、x を 2n で割ることです。このため、明示的にbig.Int.Div()メソッドを使って除算を行うことができます。

利点

• 任意の除数で割ることができる（2n に限らない）。
• 操作の意図がより明確になる（「割り算をしている」とわかる）。

欠点

• 負の数の扱いがRsh()と異なる場合があります。Div()は通常の数学的な除算を行い、big.IntのDivは0への丸め（truncate towards zero）を行います。Rshは算術右シフト（負の数の場合、マイナス無限大への丸め）と同じです。
• 2n で割る場合に比べて、Rsh()よりもわずかにパフォーマンスが劣る可能性があります。Rsh()はビット操作に特化しているため、一般的に高速です。

例

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(100)
	resultRsh := new(big.Int)
	resultDiv := new(big.Int)

	shiftBits := uint(2) // 2ビットシフト = 2^2 = 4 で割る

	// big.Int.Rsh() を使用
	resultRsh.Rsh(x, shiftBits)
	fmt.Printf("Rsh (%s を %d ビット右シフト): %s\n", x.String(), shiftBits, resultRsh.String())
	// 出力: Rsh (100 を 2 ビット右シフト): 25

	// big.Int.Div() を使用
	divisor := new(big.Int).Exp(big.NewInt(2), big.NewInt(int64(shiftBits)), nil) // 2^shiftBits を計算
	resultDiv.Div(x, divisor)
	fmt.Printf("Div (%s を %s で除算): %s\n", x.String(), divisor.String(), resultDiv.String())
	// 出力: Div (100 を 4 で除算): 25

	// 負の数での違い
	negX := big.NewInt(-100)
	negResultRsh := new(big.Int)
	negResultDiv := new(big.Int)

	negResultRsh.Rsh(negX, shiftBits)
	fmt.Printf("\nRsh (%s を %d ビット右シフト): %s\n", negX.String(), shiftBits, negResultRsh.String())
	// 出力: Rsh (-100 を 2 ビット右シフト): -25

	negResultDiv.Div(negX, divisor)
	fmt.Printf("Div (%s を %s で除算): %s\n", negX.String(), divisor.String(), negResultDiv.String())
	// 出力: Div (-100 を 4 で除算): -25

	// 厳密な違いを出す例: 奇数を負にする場合 (Rshは切り下げ、Divは0に近づける)
	oddNegX := big.NewInt(-5) // 2進数 ...111011
	divByTwo := big.NewInt(2)

	oddNegRsh := new(big.Int)
	oddNegDiv := new(big.Int)

	oddNegRsh.Rsh(oddNegX, 1) // -5 を 1ビット右シフト -> -3
	oddNegDiv.Div(oddNegX, divByTwo) // -5 / 2 -> -2 (小数点以下切り捨て)

	fmt.Printf("\nRsh (-5 を 1 ビット右シフト): %s\n", oddNegRsh.String()) // -3
	fmt.Printf("Div (-5 を 2 で除算): %s\n", oddNegDiv.String())     // -2
}

解説
正の数ではRshとDivの結果は同じになりますが、負の数で割り切れない場合に結果が異なります。Rshは算術右シフトの性質上、マイナス無限大方向へ丸めますが、Divはゼロ方向へ丸めます。この違いが重要になる場合は注意が必要です。

big.Intは内部的に数値のビット表現をバイト配列として扱います。したがって、このバイト配列を直接操作することで、ビットシフトに近い効果を得ることも理論上は可能です。ただし、これは非常に低レベルな操作であり、通常は推奨されません。

利点

• 非常に稀なケースで、big.Intメソッドでは不可能な特定のビット操作を実装する必要がある場合。
• 特定のユースケースで、カスタムのビット操作ロジックを実装する究極の柔軟性を提供します。

欠点

• 負の数や可変長の数値を正しく扱うのが非常に難しい。
• big.Intメソッドよりもパフォーマンスが劣る可能性が高い（特にRshのような最適化された操作と比較して）。
• big.Intの内部表現に依存するため、将来のGoのバージョンで動作が変わる可能性がある。
• 非常に複雑でエラーを起こしやすい。

例 (概念的、実用的ではないことが多い)

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(100)
	fmt.Printf("元の値: %s (2進数: %s)\n", x.String(), x.Text(2))

	// big.Int をバイト配列に変換
	// バイト配列はビッグエンディアン（最上位バイトが最初）
	xBytes := x.Bytes()
	fmt.Printf("バイト配列: %v\n", xBytes) // 例: [100] または [0 100] など

	// バイト配列を直接操作して右シフトを模倣する
	// 例えば、1バイト（8ビット）右シフトする場合、最初のバイトを捨てる
	// そして残りのバイトを新しい big.Int に設定する

	if len(xBytes) > 0 {
		shiftedBytes := xBytes[1:] // 最初のバイトを捨てる
		if len(shiftedBytes) == 0 {
			// 結果が0になる場合
			fmt.Printf("バイト操作による右シフト (結果0): 0\n")
		} else {
			resultByBytes := new(big.Int)
			resultByBytes.SetBytes(shiftedBytes)
			fmt.Printf("バイト操作による右シフト (1バイト): %s (2進数: %s)\n",
				resultByBytes.String(), resultByBytes.Text(2))
		}
	}

	// これはあくまで概念的な例であり、
	// 実際にはRshやDivを使うべきです。
	// ビット単位のシフトをバイト配列で行うのは非常に複雑で、
	// キャリーやパディング、負の数の扱いを考慮する必要があります。
}

解説
この方法は、特定のバイト単位の操作を行う必要がある場合にのみ検討すべきです。ビット単位のシフト操作としては、big.Int.Rsh()を使用する方が圧倒的に安全で、効率的で、正しい結果を得られます。

ほとんどの場合、big.Int.Rsh()の代替を検討する必要はありません。特に2の累乗での除算が必要な場合は、そのパフォーマンスと簡潔さからRsh()が最良の選択肢です。

• バイト配列操作
  非常に低レベルで複雑。特定のカスタムビット操作の必要性が非常に高い、かつbig.Intメソッドでは不可能な場合にのみ検討する。
• big.Int.Div()
  任意の除数で除算できる。負の数の場合は0への丸めルールに従う。汎用的な除算が必要な場合に適している。
• big.Int.Rsh()
  最も効率的で、2の累乗による除算に特化。負の数の場合は算術シフトの丸めルールに従う。