パスワードを忘れた? アカウント作成
16724477 journal
日記

nekoponの日記: 10で割った剰余 12

日記 by nekopon

割られる数をnとおきます

  • 最下位ビットを別途取っておきます(n0 = n & 1)
  • nを1ビット右シフト(n >>= 1)
  • 残りを4ビットごとに区切って和を取ります
    • n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n)
    • n = (n >> 16) + n
    • n = (n >> 8) + n
    • n &= 0xf
  • 残りが0-15になるのですが5で割った剰余を求めます
    • 表引きでもよし (tmpres = 0x0432104321043210 >> (n << 2))
    • if (((n >> 2) & 3) > (n & 3)) {
              tmpres = 5 + (n & 3) - ((n >> 2) & 3);
      } else {
              tmpres = (n & 3) - ((n >> 2) & 3);
      }
  • 上記でfloor(n/2)を5で割ったあまりが求まるので、10で割ったあまりにするには
    2倍してn0を足します (return (tmpres << 1) | n0)

これ5が22+1であるというところに鍵があったりします。

  • x ≡ 1 (mod yz) のとき x ≡ 1 (mod y)
  • x ≡ 1 (mod (x-1))
  • x ≡ 1 (mod y) ならば x2 ≡ 1 (mod y)

なので
22k ≡ 1 (mod (22k) - 1)
22k ≡ 1 (mod (2k + 1))、ゆえに
24 (=16) ≡ 1 (mod 22 + 1 (=5))、さらに
24 x 2 ≡ 1 (mod 5)
ということで4ビットごとに区切って足していけば剰余が求まるというわけです。

もひとつ

  • x ≡ -1 (mod x+1)

すなわち4 ≡ -1 (mod 5)なのが最後の if 文の表現であります。

剰余が出るだけで商は出ないので無能

15250829 journal
Android

nekoponの日記: Google v. Oracle、最高裁判決。Google勝利

日記 by nekopon


OracleとGoogleがJava APIの著作権を巡って争っていた裁判、控訴審はOracle勝利の続報。https://www.nikkei.com/article/DGXZQOGN05CPR0V00C21A4000000/

typodupeerror

日々是ハック也 -- あるハードコアバイナリアン

読み込み中...