なぜ ASCII では小文字が大文字のすぐ後ろに並んでいないのか？

 (tylerhillery.com)
1 ポイント 投稿者 GN⁺ 4 시간 전 | 1件のコメント | WhatsAppで共有
  • ASCII では Z は 90、a は 97 に配置されており、その間の 6 文字のおかげで大文字と小文字のコード差が 32 になる
  • 32 は 2^5 なので、A 65 と a 97 のように対応する大小文字は常に 00100000 の 1 ビットだけが異なる
  • この配置により、32 のビット反転値で AND すれば大文字化、32 で OR すれば小文字化、32 で XOR すれば大小文字の反転ができる
  • アルファベットの順番は文字コードに 31 を AND して下位 5 ビットだけを残せば得られ、A/a は 1、Z/z は 26 になる
  • ASCII は 7 ビットで 128 個のコードポイントだけを表現する初期の文字エンコーディングであり、現在使われている Unicode の最初の 128 個のコードポイントは ASCII と同一である

ASCII の配置と 32 の差

  • ASCII 表では大文字 Z のコード値は 90 で、小文字 a はその直後の値ではなく 97 に配置されている
  • その間には [ \ ] ^ _ ` の 6 文字がある
  • 英語のアルファベットは 26 文字で、この 6 文字を足すと 26 + 6 = 32 になる
  • 32 は 2^5 に相当する値なので、大文字と小文字の対応関係が特定の 1 ビットの違いで揃う
  • たとえば A は 65 かつ 01000001、a は 97 かつ 01100001 で、2 つの値の差は 32 である

ASCII と Unicode の関係

  • ASCII は初期の文字エンコーディング方式の 1 つで、7 ビットだけを使って 2^7 = 128 個のコードポイントを表す
  • 128 個のコードポイントでは、人が使うすべての文字を収めるには不十分であり、とくに数万字を持つ中国語のような言語まで収めるには足りない
  • 現在の標準文字集合としては Unicode が使われており、UTF-8 や UTF-16 のような複数のエンコーディングを持つ
  • Unicode の最初の 128 個のコードポイントは ASCII と同一である

大小文字を分ける 5 ビット目

  • 大文字と対応する小文字を 2 進数で比較すると、常に 32 に相当するビットが切り替わる
65  = 01000001 = A
97  = 01100001 = a

66  = 01000010 = B
98  = 01100010 = b

67  = 01000011 = C
99  = 01100011 = c
  • 32 は 2 進数で 00100000 であり、この 1 ビットが大文字と小文字の違いを生む
  • ASCII のアルファベット配置は、ビット演算で大小文字変換を簡単にできるようになっている

ビット演算で大小文字を処理する

  • 大文字に変換

    • 文字を大文字にするには、32 のビット反転値とのビット AND を行う
0 1 1 0 0 0 0 1 (97 = 'a')
& 1 1 0 1 1 1 1 1 (mask)
-------------------
0 1 0 0 0 0 0 1 (65 = 'A')
  • a に適用すると 97 が 65 に変わって A になる
  • すでに大文字の A に同じ演算を適用すると、そのまま A のままになる

  • 小文字に変換

    • 文字を小文字にするには、32 とのビット OR を行う
0 1 0 0 0 0 0 1 (65 = 'A')
| 0 0 1 0 0 0 0 0 (32)
-------------------
0 1 1 0 0 0 0 1 (97 = 'a')
  • A に適用すると 65 が 97 に変わって a になる
  • すでに小文字の a に同じ演算を適用すると、そのまま a のままになる

  • 大小文字の反転

    • 大小文字を反転させるには、32 とのビット XOR を行う
0 1 1 0 0 0 0 1 (97 = 'a')
^ 0 0 1 0 0 0 0 0 (32)
-------------------
0 1 0 0 0 0 0 1 (65 = 'A')

0 1 0 0 0 0 0 1 (65 = 'A')
^ 0 0 1 0 0 0 0 0 (32)
-------------------
0 1 1 0 0 0 0 1 (97 = 'a')
  • a は A に、A は a に変わる

下位 5 ビットでアルファベット順を得る

  • アルファベットの順番は、文字コードに 31 をビット AND して求められる
0 1 0 0 0 0 0 1 (65 = 'A')
& 0 0 0 1 1 1 1 1 (31)
-------------------
0 0 0 0 0 0 0 1 (1)

0 1 1 1 1 0 1 0 (122 = 'z')
& 0 0 0 1 1 1 1 1 (31)
-------------------
0 0 0 1 1 0 1 0 (26)
  • 31 は 2 進数で 00011111 なので、先頭側のビットを消して下位 5 ビットだけを残す
  • ASCII ではアルファベット文字の下位 5 ビットがアルファベット上の位置と一致する
  • A/a は 00001 で終わるので 1、B/b は 00010 で終わるので 2、Z/z は 11010 で終わるので 26 になる
  • ASCII 文字コードで c & 31 は c % 32 と同じである
  • 32 が 2 のべき乗であるため、31 でマスクすると 32 単位のまとまりを取り除き、残りの部分だけを保持する
'A' = 65  → 65 % 32 = 1
'B' = 66  → 66 % 32 = 2
...
'Z' = 90  → 90 % 32 = 26
'a' = 97  → 97 % 32 = 1
'b' = 98  → 98 % 32 = 2
...
'z' = 122 → 122 % 32 = 26

関連記事

1件のコメント

 
GN⁺ 4 시간 전
Lobste.rsの意見

  • 説明としては悪くないが、https://garbagecollected.org/2017/01/31/four-column-ascii/ のほうがよりうまく説明している気がする
    単に Shift だけの問題ではなく、Ctrl も関係している。たとえば Tab は Ctrl-I だが、I は 1001001 で、Ctrl が先頭ビットをマスクして Tab の 0001001 を残すからだ

  • 1960年代のメーカーのように電子論理ではなく 電気機械式論理 を使うなら、bit paired keyboard のほうがずっと実装しやすい
    Shift キーは ASCII 文字のビットを1つトグルするだけでよい。今ではどのキーボードにも汎用 CPU が入っていて論理は事実上ただ同然だが、汎用コンピュータが部屋ひとつ分の大きさだった時代には、そうした解決策のほうがはるかに高価だった

  • 記事は ASCII 配置の動機として、大文字・小文字変換を ビット演算 で効率よく実装できる点を挙げているが、その価値は歴史的にはともかく現代ではかなり薄いように見える
    a→A 変換は単純なテキストでしか通用せず、ISO-8859-1 や Unicode が ü、ç のような文字にもこの配置を一部拡張していたとしても、大文字・小文字変換は地域・文脈・時代によって変わる。ß や ï の正しい大文字/小文字対応は、言語、規制機関、利用地域、時代に左右される
    Unicode は https://www.unicode.org/charts/case/ のような大文字小文字マッピングや case folding 表を提供していて、一般的なケースにはかなり近い答えを出せるが、人間の方針が介在する問題なので複雑さは事実上無限で、正しく扱うには専用ソフトウェアが必要になりうる
    今日では Unicode の最初の 2⁷ コードポイントにしか制限されないと保証できない限り、0b0010_0000 のオフセットは簡単に破綻し、単一のビット演算より高コストなコードパスが必然的に入る。CPython でも ''.upper は unicode_upper{,_impl} の ASCII 高速パスを通るが、実際には 分岐、インライン関数、構造体アクセス、複数の 関数 と 関数、マクロ を経て、テーブル参照 を行っている
    現代の言語における ''.upper の実装はおおむね同程度の複雑さを持つだろうし、コンパイラが最適化したとしても、現代的なアプローチは単一ビット演算より高価にならざるをえないように見える。この設計の利点が際立つのは、生のバイナリや 2⁷ 以下のコードポイントの Unicode データを持つ dtype=uint8 の numpy.ndarray に算術演算を行うような専用ソフトウェアくらいだろう
    気になるのはここだ。この設計選択の唯一の動機が記事のいうそれだったと仮定すると、当時でも 128バイトのルックアップテーブル という代替案があったはずだが、コンピューティングの歴史において、単一ビット演算が 128 バイトのテーブル参照より効率的、あるいは実現しやすかった時期はいつだったのだろうか？

    • 長く成功した大衆技術を掘り下げると、この種の ビットトリック はよく見かける
      ある時点の設計選択が、後になって破綻する前提に依存して何かの形を固定し、その後の拡張を難しくしたり不可能にしたりする。最近の IPv6 関連の記事でも、IPv4 と IPv6 における当時は正しかった選択が、今日では巨大な負担になっていることが見て取れる
      好意的に見れば、こうした選択はリスクと利益を天秤にかけて下されたのだろう。「文字1つを大文字にするのに単一ビット演算ならずっと速いのだから、いつか日本語ユーザーが現れたときに破綻するリスクを負う価値がある」といった具合だ
      現代人の立場からすると、1976年の選択が 2026年の生活をより難しくしているが、1976年にコンピュータを持てなかったなら、その利益は享受できず欠点だけが残る。こうした利己性を脇に置いてみると、20年後にも人気があるソフトウェアを作るとして、このような選択の 持続可能性 をどうすればもっと適切に予測できるのか気になる
    • ASCII 専用の 大文字小文字無視 エンコーディングを使うネットワークプロトコルは多く、高速なビット単位の tolower は今でも有用だ。https://dotat.at/@/2022-06-27-tolower-swar.html

  • 少なくとも ASCII では文字が連続している。EBCDIC では間隔が 0x40（64）で、ASCII と比べると 9文字の行が2つと 8文字の行が1つ、上下に積み重なったような形になっている
    https://en.wikipedia.org/wiki/EBCDIC

  • IRC のニックネームが ASCII 大文字小文字無視 だったので、foo{ が foo[ と同じで、bar| が bar\ と同じだったのを思い出す
    このせいで今でも一部のクライアントが混乱していても驚かない