https://leetcode.com/problems/sum-of-two-integers/solution/ で登場したのでざっとまとめる。
いや、ただ箇条書きで垂れ流す。
常識
- 32bit整数において、「負の数である」 <=> 「1ビット目が1」
- 基数 = n進数のn
- 基数の補数(complement) = ある自然数を2進数(2進法)で表現した時に、足し合わせるとちょうど2のべき乗となる最小の数(一桁増えて先頭が1、残りが0となる数)
- 減基数の補数 = 基数の補数 - 1 = ギリギリ桁の上がらない最大の数 = 元の数のbit反転
(https://unskilled.site/%E3%80%90%EF%BC%91%E3%81%AE%E8%A3%9C%E6%95%B0%E3%81%A8%E3%81%8B%E3%80%91%E8%A3%9C%E6%95%B0%E3%82%92%E7%90%86%E8%A7%A3%E3%81%97%E3%81%9F%E3%81%84%E3%81%A7%E3%81%99%E3%80%90%EF%BC%92%E3%81%AE%E8%A3%9C/ より)
肝心なとこ
ある正の数xについて、-xは、xの基数の補数である
つまり、負の数-xのbit配列を求めるには、「xの基数を求める」= 「xをbit反転し、最小位に1を加える」という方法で求める必要がある。
このような負の数のbit配列の決め方は、コンピュータが引き算を(簡単に?)実行できるようにするための工夫である。(具体的な方法は、See: https://unskilled.site/%E3%80%90%EF%BC%91%E3%81%AE%E8%A3%9C%E6%95%B0%E3%81%A8%E3%81%8B%E3%80%91%E8%A3%9C%E6%95%B0%E3%82%92%E7%90%86%E8%A7%A3%E3%81%97%E3%81%9F%E3%81%84%E3%81%A7%E3%81%99%E3%80%90%EF%BC%92%E3%81%AE%E8%A3%9C/)
Ref
以下がわかりやすかった。