前につぶやきSNSに上げたけど、ここにも置いておく。
環境としてはC言語系統を想定。
64ビットを整数型の最大のビット数とする処理系において、
2^64(2の64乗)を引数xで割った余りを返す関数
uint64_t Modulo2P64(uint64_t x) { ... }
を実装せよ。
補足:
・uint64_tは64ビット符号なし整数型である。
・標準関数をはじめ如何なる外部関数やマクロを使用してはならない。
・引数xに0を指定することはできないが、その引数チェックはしなくてよい。
・制御構文を使ったら70点、1つの式(1つのreturn文)で記述できたら100点
更に補足:(2^64)は2の64乗です。66じゃないです。
んで、答えは↓の方。クイズノックっぽく!
模範解答:
uint64_t Modulo2P64(uint64_t x) { return (~x + 1) % x; }
最初友人に出して返ってきた答え:
uint64_t Modulo2P64(uint64_t x) { const uint64_t UI2P63 = 1UI64 << 63; return UI2P63 < x ? UI2P63 - (x - UI2P63) : ((UI2P63 % x) * 2) % x; }
最初に僕が用意しておいた答え:
uint64_t Modulo2P64(uint64_t x) { return (0xffffffffffffffff % x + 1) % x; }
それがいいなら、これでもいいじゃんみたいな答え:
uint64_t Modulo2P64(uint64_t x) { return (uint64_t)-(sint64_t)x % x; }
ようわからんけど、これでもいいだろみたいな答え:
uint64_t Modulo2P64(uint64_t x) { return ((0xffffffffffffffff - x) + 1) % x; }
その後ごにょごにょ友人と話した結果、上の模範解答になりましたとさ。。。