ビット演算で商と剰余の最大ビット数は?

　いきなりですが問題です．

「x, yがともにnビットのとき，商と剰余は最大nビット」について，具体例をそれぞれ示しなさい．

　上の出題文の不備を指摘し，修正しましょう．

　元ネタは先週のセキュリティの授業です．RSA暗号アルゴリズムの解説にあたり，基礎となる算術演算（加減乗除と剰余）を1枚のスライドにしていました．小数や分数は考えませんので，除算（x / y）の結果は整数です（例えば7 / 3は2）．剰余演算はC言語の表記を借りてx % yと表します（例えば7 % 3は1）．
　計算機上で，整数値はビットの並び（ビット列），そして符号なし整数として表されることを想定したとき，nビット同士の和（x + y）は，n+1ビットになることがあります．そのため「x, yがともにnビットのとき，和は最大n+1ビット」と言えます．差は，負の数をどのように表現するかを取り決めておく必要がありますが，加法の逆演算と捉えると，n+1ビットあればいいかなとなります．
　積は，nビット同士で最大2nビットです．符号なし整数で，すべてが1のビット列となる整数値を，筆算するのでもいいし，文字式を用いて $(2^{n}-1)^2$ を展開するのでも，2nビットの数になることが分かります．
　前振りが長くなりましたが，x / yが最大になるのは，被除数のxは，nビットで表せる値のうちの最大値，除数のyは，nビットで表せる値のうち0を除いた最小値のときです．
　「nビットで表せる値のうちの最大値」を，nの式で表すと，積のときにも書いた $2^{n}-1$ です．同様に「nビットで表せる値のうち0を除いた最小値」は，1なのですが，これを「x, yがともにnビットのとき」と見なしてよいのかについて，注意が必要となります．
　「n次の多項式」と書いたときにn次の係数が0でないのと同じように，「nビット」と表記するとき，最上位ビットは1であることが，要請されているようにも見えるからです．例えばn=3とすると，3ビットで表される数というを，000から111まで（0から7まで）と考える人もいれば，100から111まで（4から7まで）と考える人もいるかもしれません．後者の考えでは，010は「2ビットの数」と解釈します．
　このような曖昧さを排除するため，授業中に次のように，指示を追加しました．

ビット列は符号なし整数とみなしてよい．xとyはnビット未満（nビットで表したときの最上位ビットが0）でもよいが，結果はnビット（nビットで表したときの最上位ビットは1）とすること．

　続いて問題です．今回の問題（「x, yがともにnビットのとき，商と剰余は最大nビット」）について，読んでなるほどと思ってもらえる答案を作りましょう．
　検討していきます．「nビットで表せる値のうちの最大値」をどのように表現するかを考えます．候補は次の3つです．

ビット列（0と1の並び）で表す：1...1
日本語で表す：全てのビットが1
文字式で表す： $2^{n}-1$

　文字式で表すとき，商の最大値は，上に書いたとおり， $x=2^{n}-1$ ， $y=1$ のときで，演算の結果はxです．剰余の最大値は， $y=2^{n}-1$ ， $x=y-1=2^{n}-2$ ，のときで，この演算の結果もxとなります． $2^{n}-2$ をビット列で表すと，1...10です．
　商が最大のときのxと，剰余が最大のときのyが，等しくなります．そして商が最大のときのyのビット列と，剰余が最大のときのxのビット列が，反転の関係にあります．
　以上をもとに，日本語で表すのがいいでしょう．次のようになります．