317
правок
Изменения
→Явная формула для получения зеркального двоичного кода Грея
Для любого <tex>x < 2^n</tex> выполняется <tex>\enskip L_x = 0M_x</tex> и, по условию, равно
<tex>L_x = 0(x_{n-1}x_{n-2}... \dots x_{0} \oplus 0x_{n-1}x_{n-2}... \dots x_{1})</tex> раскрыв скобки, получим новое выражение <tex>L_x</tex>:
<tex>= 0x_{n-1}x_{n-2}... \dots x_{0} \oplus 00x_{n-1}x_{n-2}... \dots x_{1}</tex> что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)
<tex>= x \oplus (\lfloor x / 2 \rfloor)</tex>
Для любого <tex>x \leqslant 2^n</tex> выполняется <tex>\enskip L_x = 1</tex><tex>M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть
<tex>L_x = 1(\overline {x_{n-1} x_{n-2}... \dots x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2}... \dots x_{1}})</tex> что по свойству '''xor''' (<tex>\neg x \oplus \neg y = x \oplus y</tex>) равно
<tex>= 1(\overline {x_{n-1}}x_{n-2}... \dots x_{0} \oplus 0x_{n-1}x_{n-2}... \dots x_{1})</tex> или (все по тому же свойству)
<tex>= 1(x_{n-1}x_{n-2}... \dots x_{0} \oplus 1x_{n-1}x_{n-2}... \dots x_{1})</tex> раскрыв скобки, получим
<tex>= 1x_{n-1}x_{n-2}... \dots x_{0} \oplus 01x_{n-1}x_{n-2}... \dots x_{1}</tex> откуда получаем, зная из условия, что старший разряд <tex>L_x</tex> равен <tex>1</tex>
<tex>= x_{n}x_{n-1}x_{n-2}... \dots x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}... \dots x_{1}</tex> что, аналогично первому пункту, равно
<tex>= x \oplus (\lfloor x / 2 \rfloor)</tex>
