/
grey_code.go
51 lines (44 loc) · 1.25 KB
/
grey_code.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package args
import "math/bits"
// Converts a linear binary number to a binary-reflected grey code
func Grey(v uint) uint {
return v ^ (v >> 1)
}
// Converts a binary-reflected grey code to a linear binary number
func FromGrey(g uint) uint {
if bits.UintSize == 64 {
g ^= g >> 32
}
g ^= g >> 16
g ^= g >> 8
g ^= g >> 4
g ^= g >> 2
g ^= g >> 1
return g
}
// Gives a grey-code increment for the given binary. Result always has only one non-zero bit.
// The following is always true: Grey(v) ^ GreyInc(v) == Grey(v + 1)
func GreyInc(v uint) uint {
// This can also be calculated in a classical way with parity (count non-zero bits) of value, but it will be slower
//
// Classical gray_inc(x):
// if parity of x is even:
// return x ^ 1
// if parity of x is odd:
// y := rightmost 1 bit in x
// return x ^ (y << 1)
//
// The fastest way is the shorter version of Grey(v) ^ Grey(v+1)
return Grey(v ^ (v + 1))
}
// Returns a bit (offset) that will change in grey-code equivalent of v on incrementing it
// The following is always true: 1<<GreyIncBit(v) == GreyInc(v)
func GreyIncBit(v uint) uint8 {
if v&1 == 0 {
return 0 // a faster way
}
return greyIncBitCalc(v)
}
func greyIncBitCalc(v uint) uint8 {
return uint8(bits.Len(GreyInc(v)) - 1)
}