奇数を奇数で割るときに下位ビットから引き算してみるというだけの話

tune3orz(ワクチン慎重派) @tune3orz

(2m+1 | 2a+1) ⇔ (m-a | 2a+1)

tune3orz(ワクチン慎重派) @tune3orz

@tune3orz 例: (65|5)⇔(32-2|5)

tune3orz(ワクチン慎重派) @tune3orz

@tune3orz 例: (65|13)⇔(32-6|13)

tune3orz(ワクチン慎重派) @tune3orz

役に立ちそで役に立たない法則…

tune3orz(ワクチン慎重派) @tune3orz

@tune3orz 2進表記になっていれば、割り算を使わずに、引き算とビットシフトだけで、割りきれるかどうかを判定できるということになるが、それほどメリットがあるとも思えない…

tune3orz(ワクチン慎重派) @tune3orz

2m+1が2a+1で割りきれるときは、 2m+1=(2a+1)(2b+1) と書けるから、 (2m+1)/(2a+1)=2b+1 (m-a)/(2a+1)=b つまりこれは商を下位ビットから求めているのか。

tune3orz(ワクチン慎重派) @tune3orz

reading: ユークリッドの互除法 - Wikipedia ja.m.wikipedia.org/wiki/%E3%83%A6…