Author: Gerd Isenberg
Date: 14:25:07 07/11/03
Go up one level in this thread
On July 11, 2003 at 09:47:17, Walter Faxon wrote:
>Matt's magic number for the 64-bit lsb is: 2015959759.
Some "de Bruijn" properties of Matt's magic constant:
2015959759 or 0x78291ACF
or binary
01111000001010010001101011001111
Sequence of 6bit groups from high to low:
bin dec
bit 31 - bit 26 011110 30
bit 30 - bit 25 111100 60
bit 29 - bit 24 111000 56
bit 28 - bit 23 110000 48
bit 27 - bit 22 100000 32
bit 26 - bit 21 000001 1
bit 25 - bit 20 000010 2
bit 24 - bit 19 000101 5
bit 23 - bit 18 001010 10
bit 22 - bit 17 010100 20
bit 21 - bit 16 101001 41
bit 20 - bit 15 010010 18
bit 19 - bit 14 100100 36
bit 18 - bit 13 001000 8
bit 17 - bit 12 010001 17
bit 16 - bit 11 100011 35
bit 15 - bit 10 000110 6
bit 14 - bit 9 001101 13
bit 13 - bit 8 011010 26
bit 12 - bit 7 110101 53
bit 11 - bit 6 101011 43
bit 10 - bit 5 010110 22
bit 9 - bit 4 101100 44
bit 8 - bit 3 011001 25
bit 7 - bit 2 110011 51
bit 6 - bit 1 100111 39
bit 5 - bit 0 001111 15
Unique values, a valid 6bit de Bruijn sequence, in 32 bit not so hard.
The next thing i tried is a 5 bit sequence, which is harder for 32 bit.
The last bit 0 was wrong.
bin dec
bit 31 - bit 27 01111 15
bit 30 - bit 26 11110 30
bit 29 - bit 25 11100 28
bit 28 - bit 24 11000 24
bit 27 - bit 23 10000 16
bit 26 - bit 22 00000 0
bit 25 - bit 21 00001 1
bit 24 - bit 20 00010 2
bit 23 - bit 19 00101 5
bit 22 - bit 18 01010 10
bit 21 - bit 17 10100 20
bit 20 - bit 16 01001 9
bit 19 - bit 15 10010 18
bit 18 - bit 14 00100 4
bit 17 - bit 13 01000 8
bit 16 - bit 12 10001 17
bit 15 - bit 11 00011 3
bit 14 - bit 10 00110 6
bit 13 - bit 9 01101 13
bit 12 - bit 8 11010 26
bit 11 - bit 7 10101 21
bit 10 - bit 6 01011 11
bit 9 - bit 5 10110 22
bit 8 - bit 4 01100 12
bit 7 - bit 3 11001 25
bit 6 - bit 2 10011 19
bit 5 - bit 1 00111 7
bit 4 - bit 0 0111x 15 corrected to 14 by -1
2015959759 - 1 is a valid 5-bit de Bruijn Sequence.
Are there more numbers with this property?
Cheers,
Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.