Вот наивная тест для конкретного кода Грея монотонного упорядочения (двоичный отраженный код Грея):
// convert Gray code binary number to base 2 binary number
int Base2(byte Gray){ Gray^=Gray>>4; Gray^=Gray>>2; return Gray^=Gray>>1; }
// test if Gray codes are consecutive using "normal" base 2 numbers
boolean GraysAdjacent(byte x, byte y){ return 1 == abs(Base2(x)-Base2(y)); }
видеть особенно этот ответ (лучше всего):
How to find if two numbers are consecutive numbers in gray code sequence
закодированный в C, как :
int GraysTouch(byte x, byte y){ return !((x^y^1) && (x^y^(y&-y)<<1)); }
// test x marks the spots! (where they touch!)
for(int i=31; i>-1; --i)
for(int j=31; j>-1; --j)
Serial.print((String)(GraysTouch(i^i>>1, j^j>>1)?"x":".") +
(GraysTouch(j^j>>1, i^i>>1)?"X":".") + (j?"":"\n"));
Как это работает: ... будет объяснено и не код OP, потому что он очень подозрительный (см. Комментарий ниже).
Свойство XOR, ака оператора ^, что биты, которые соответствуют являются 0 и биты, которые отличаются 1.
1^0 == 0^1 == 1
1^1 == 0^0 == 0
Кроме того, на некоторое время, 0 XOR b работает как тождественной функции или просто b
и
1 XOR b работает как дополнение (без комплиментов, пожалуйста) функции или ~b.
id(x) == x == x^0
opposite(x) == ~x == x^11111111 Why eight 1's? Are eight enough?
При сравнении двух битовых строк с XOR, биты, которые отличаются XOR в 1, в противном случае биты MUST матч и XOR является 0:
0101 0001111001100111000
XOR 0011 XOR 0001111001100000111
------ ---------------------
0110 0000000000000111111
Это объясняет x^y часть из код выше.
----------------------------------------------- -----------------------
Отклонение:
n^n>>1 выполняет быструю конвертацию двоичных чисел базы 2 в двоичные числа серого кода, используемые здесь.
Также обратите внимание, насколько сильно это f(a,b)=a^b^b=a является идемпотентным для любых b!
На месте своп находится a=a^b; b=a^b; a=a^b;.
Unrolled c=a^b; d=c^b; e=c^d; ie. d=a^b^b=a; e=a^b^a=b;
---------------------------------------------- ------------------------
Теперь по определению для двух серых кодированных чисел смежны или подряд там должен быть один и только один бит, который может измениться и быть другим.
Примеры:
Johnson
Code
000 000 000 000
001 001 001 100
011 101 011 110
111 111 010 010
110 011 110 011
100 010 111 111
110 101 101
100 100 001
^^^
this Gray coding
is the one used here
Изучите его внимательно.
Случай 1
Когда низшего порядка бит последовательных чисел, x и y, для любой из кодов Грея, различны, остальные должны быть одинаковыми! Это определение серого кода. Это означает, что x^yдолжен выглядеть 0000 ... 0001.
Помните о дополнении, функции ~ aka 1^b? Для тестирования последнего бита x^y составляет XOR 'd с 1.
Этим объясняется x^y^1.
-------------------------------------------
Корпус 2
Местоположение другого бита в последовательных серых кодовых номерах x и y не является младшим разрядом. Посмотрите внимательно на последовательные номера серого кода.
001 010 101 lower order bits all match
011 110 111
| | | <-- | mark location of lowest 1
010 100 010 <-- XOR's
Интересно, что в это код Грея, когда низкие биты порядка совпадают в x и y, так что тоже делает расположение низшего порядка 1.
Еще более интересным является то, что для последовательных чисел, биты всегда разные (для это Серого кода) в битовой позиции заказа следующего выше!
Так, x^y выглядит ???...?1000...0 где 1000...0 должен иметь по крайней мере один 0, 10 (почему?) И ???...? являются загадка бит, что для последовательных цифр коды Грея должна быть 000...0. (Почему? Е. Быть последовательными x^y должны выглядеть ...)
Наблюдение что
x^y looks like ???...?100...0 if and only if
x and y look like ???...?:10...0
| <-- remember? the 1 location !!
| местоположение можно найти либо x&-x или y&-y. (Почему? Почему должен ли - быть сделано с помощью комплемента машины к 2-?)
Однако : место должно быть проверено, что 1 (почему?) И ???...? являются 000...0. (Почему?)
Так,
x^y looks like ???...?100...0 and
(y&-y)<<1 looks like 000...0100...0
и это объясняет тест x^y^((y&-y)<<1).
----------------------------------------------- --------------------
Почему это работает: ... является следствием свойств конкретного кода Gray, используемого здесь. Экзамен и объяснение слишком сложны для того, чтобы объяснить, почему этот серый код должен иметь эти свойства.
--------------------------------------------- -------------------------
Комментарий к неадекватности предыдущих ответов из-за проблем с кодом OP.
Caveat 1: Просто быть явным, алгоритм в вопросе Ор по:
private static int graycode(byte term1, byte term2) {
byte x = (byte)(term1^term2); // why use XOR?
int count = 0;
while(x!=0)
{
x = (byte)(x &(x-1)); // why use bitwise operator?
count++; // what is count?
}
return count == 1;
}
имеет интересную интерпретацию последовательных кодов Грея. Он правильно сообщает, когда любые две двоичные последовательности отличаются в одной битовой позиции.
Если по последовательным кодам подразумевается, что коды Grey используются для перечисления монотонного порядка, возникает проблема.
В частности, код будет возвращать true для всех этих пар:
000, 001 or 000, 010 or 000, 100
так упорядочение может быть 001, 000, 010 но где можно 100 идти? Алгоритм сообщает (правильно), что «последовательность» 100 с любым из 001 or 010 - false.
Таким образом 100 должен непосредственно предшествовать или следовать 000 в перечислении, но не может непосредственно предшествовать или следовать за 001 или 010. DOH !!!
Caveat 2: Примечание x = (byte)(x & (x-1)) сбрасывает низкий порядка 1 бит x к нулю.
рефов:
Gray code increment function
Deriving nth Gray code from the (n-1)th Gray Code
https://electronics.stackexchange.com/questions/26677/3bit-gray-counter-using-d-flip-flops-and-logic-gates
How do I find next bit to change in a Gray code in constant time?
How to find if two numbers are consecutive numbers in gray code sequence
Возможный дубликат [Как найти, если два числа последовательных чисел в серой кодовой последовательности] (HTTP: // StackOverflow .com/questions/27218894/how-to-find-if-two-numbers-are-sequence-numbers-in-gray-code-sequence) – Morwenn
N что два соседа в коде Grey отличаются только одним битом (это то, что выполняет ваша функция), но два числа, отличающиеся только битом, не всегда являются соседями в коде Grey: коды Grey 1000 и 1010 отличаются только одним битом, но не являются соседями (1000 и 1010 соответственно равны 15 и 12 в десятичной форме). – Morwenn