1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43

package numeric

var interleaveMagic = []uint64{
	0x5555555555555555,
	0x3333333333333333,
	0x0F0F0F0F0F0F0F0F,
	0x00FF00FF00FF00FF,
	0x0000FFFF0000FFFF,
	0x00000000FFFFFFFF,
	0xAAAAAAAAAAAAAAAA,
}

var interleaveShift = []uint{1, 2, 4, 8, 16}

// Interleave the first 32 bits of each uint64
// apdated from org.apache.lucene.util.BitUtil
// which was adapted from:
// http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
func Interleave(v1, v2 uint64) uint64 {
	v1 = (v1 | (v1 << interleaveShift[4])) & interleaveMagic[4]
	v1 = (v1 | (v1 << interleaveShift[3])) & interleaveMagic[3]
	v1 = (v1 | (v1 << interleaveShift[2])) & interleaveMagic[2]
	v1 = (v1 | (v1 << interleaveShift[1])) & interleaveMagic[1]
	v1 = (v1 | (v1 << interleaveShift[0])) & interleaveMagic[0]
	v2 = (v2 | (v2 << interleaveShift[4])) & interleaveMagic[4]
	v2 = (v2 | (v2 << interleaveShift[3])) & interleaveMagic[3]
	v2 = (v2 | (v2 << interleaveShift[2])) & interleaveMagic[2]
	v2 = (v2 | (v2 << interleaveShift[1])) & interleaveMagic[1]
	v2 = (v2 | (v2 << interleaveShift[0])) & interleaveMagic[0]
	return (v2 << 1) | v1
}

// Deinterleave the 32-bit value starting at position 0
// to get the other 32-bit value, shift it by 1 first
func Deinterleave(b uint64) uint64 {
	b &= interleaveMagic[0]
	b = (b ^ (b >> interleaveShift[0])) & interleaveMagic[1]
	b = (b ^ (b >> interleaveShift[1])) & interleaveMagic[2]
	b = (b ^ (b >> interleaveShift[2])) & interleaveMagic[3]
	b = (b ^ (b >> interleaveShift[3])) & interleaveMagic[4]
	b = (b ^ (b >> interleaveShift[4])) & interleaveMagic[5]
	return b
}