これは忘備録

研究しててハミング重み使っていてこねくり回したときのもの．ハミング重みをこんな使い方をすることは中々ないであろう内容．知らんけど．

定義

定義（ハミング重み）ここでは， $2$ 進数に直したときの $1$ の個数とし， $\displaystyle k \in \mathbb{N}$ に対して $\mathcal{H}\left(k\right)$ と表すことにする．

例えば， $\mathcal{H}\left(2\right)=1$ ， $\mathcal{H}\left(20\right)=2$ ， $\mathcal{H}\left(31\right)=5$ ．

定理的なもの

定理（ハミング重み）

$\displaystyle k \in \mathbb{N}$ とする．但し， $3$ つ目は $k\geq 1$ ．

\begin{aligned} \mathcal{H}\left(2k\right)&=\mathcal{H}\left(k\right)\\\ \mathcal{H}\left(2k+1\right)&=\mathcal{H}\left(k\right)+1\\\ \mathcal{H}\left(2k - 1\right)&=\mathcal{H}\left(k - 1\right)+1 \end{aligned}

証明の概略

$1$ つ目は簡単で，右にビットシフトしてもLSBは $0$ なので $1$ の個数は変わらない．

$2$ つ目は，LSBが $1$ であることに注意して，その後 $1$ を使う． \begin{aligned} \mathcal{H}\left(2k+1\right)&=\mathcal{H}\left(2k\right)+1\\ &=\mathcal{H}\left(k\right)+1 \end{aligned}

$3$ つ目も基本的に同様． \begin{aligned} \mathcal{H}\left(2k - 1\right)&=\mathcal{H}\left(2\left(k - 1\right)+1\right)\\ &=\mathcal{H}\left(2\left(k - 1\right)\right)+1 \\ &=\mathcal{H}\left(k - 1\right)+1 \end{aligned}