З попередніми кодами я завершив. Тепер переходимо до бітових циклів de Bruijn, будемо їх ґенерити. Найменші послідовності можна перебрати без компа.
Bits: 1, Length: 2, Count: 1
0x01 : 0b-1
Bits: 2, Length: 4, Count: 1
0x03 : 0b--11
Bits: 3, Length: 8, Count: 2
0x17 : 0b---1-111
0x1D : 0b---111-1
Тут можуть виникнути питання:
"0b це шо ?" : В останіх версіях C# це префікс двійкового числа.
"Чому мінуси ? (-)" : Я замінив '0' на '-' щоб візуально було легше читати, щоб бачити властивості.
"Це ж не всі послідовності, Де 0xE8 : 0b111-1--- ?" : Залежить як порівнювати. Якщо існує спосіб циклічно змістити послідовність біт A і отримати послідовність біт B, то такі послідовності будемо вважати рівними (A == B). [0xE8 == (0x1D << 3)]
Всі цикли будемо вирівняти так щоб в старших бітах були нулі.
4 <= 16 (зґенерив і перевірив всі)
Bits: 4, Length: 16, Count: 16
0x09AF : 0b----1--11-1-1111
0x09EB : 0b----1--1111-1-11
0x0A6F : 0b----1-1--11-1111
0x0A7B : 0b----1-1--1111-11
0x0B3D : 0b----1-11--1111-1
0x0B4F : 0b----1-11-1--1111
0x0BCD : 0b----1-1111--11-1
0x0BD3 : 0b----1-1111-1--11
0x0CBD : 0b----11--1-1111-1
0x0D2F : 0b----11-1--1-1111
0x0D79 : 0b----11-1-1111--1
0x0DE5 : 0b----11-1111--1-1
0x0F2D : 0b----1111--1-11-1
0x0F4B : 0b----1111-1--1-11
0x0F59 : 0b----1111-1-11--1
0x0F65 : 0b----1111-11--1-1
▼5 <= 32 (зґенерив всі і тести пройшли всі)
Bits: 5, Length: 32, Count: 2048
0x04653ADF : 0b-----1---11--1-1--111-1-11-11111
0x04653B5F : 0b-----1---11--1-1--111-11-1-11111
0x04653EB7 : 0b-----1---11--1-1--11111-1-11-111
0x04653ED7 : 0b-----1---11--1-1--11111-11-1-111
0x046569DF : 0b-----1---11--1-1-11-1--111-11111
0x046569F7 : 0b-----1---11--1-1-11-1--11111-111
0x04656E9F : 0b-----1---11--1-1-11-111-1--11111
0x04656FA7 : 0b-----1---11--1-1-11-11111-1--111
0x0465769F : 0b-----1---11--1-1-111-11-1--11111
0x04657DA7 : 0b-----1---11--1-1-11111-11-1--111
0x0465A9DF : 0b-----1---11--1-11-1-1--111-11111
0x0465A9F7 : 0b-----1---11--1-11-1-1--11111-111
0x0465BA9F : 0b-----1---11--1-11-111-1-1--11111
0x0465BEA7 : 0b-----1---11--1-11-11111-1-1--111
0x0465DA9F : 0b-----1---11--1-111-11-1-1--11111
0x0465F6A7 : 0b-----1---11--1-11111-11-1-1--111
0x04674ADF : 0b-----1---11--111-1--1-1-11-11111
0x046752DF : 0b-----1---11--111-1-1--1-11-11111
0x0467695F : 0b-----1---11--111-11-1--1-1-11111
0x04676A5F : 0b-----1---11--111-11-1-1--1-11111
0x0467D2B7 : 0b-----1---11--11111-1--1-1-11-111
0x0467D4B7 : 0b-----1---11--11111-1-1--1-11-111
0x0467DA57 : 0b-----1---11--11111-11-1--1-1-111
0x0467DA97 : 0b-----1---11--11111-11-1-1--1-111
0x046959DF : 0b-----1---11-1--1-1-11--111-11111
0x046959F7 : 0b-----1---11-1--1-1-11--11111-111
0x04695CFB : 0b-----1---11-1--1-1-111--11111-11
0x04695D9F : 0b-----1---11-1--1-1-111-11--11111
0x04695F3B : 0b-----1---11-1--1-1-11111--111-11
0x04695F67 : 0b-----1---11-1--1-1-11111-11--111
0x0469CAFB : 0b-----1---11-1--111--1-1-11111-11
0x0469D95F : 0b-----1---11-1--111-11--1-1-11111
...
0x04A367D7 : 0b-----1--1-1---11-11--11111-1-111
...
0x04EB1BE5 : 0b-----1--111-1-11---11-11111--1-1
...
0x0564EF8D : 0b-----1-1-11--1--111-11111---11-1
...
0x05F26A3B : 0b-----1-11111--1--11-1-1---111-11
...
0x067DC5A9 : 0b-----11--11111-111---1-11-1-1--1
...
0x0717D935 : 0b-----111---1-11111-11--1--11-1-1
...
0x07C535D9 : 0b-----11111---1-1--11-1-111-11--1
...
0x07DC4CB5 : 0b-----11111-111---1--11--1-11-1-1
...
0x07DC5699 : 0b-----11111-111---1-1-11-1--11--1
0x07DC5935 : 0b-----11111-111---1-11--1--11-1-1
0x07DC59A9 : 0b-----11111-111---1-11--11-1-1--1
0x07DC5A99 : 0b-----11111-111---1-11-1-1--11--1
0x07DC8A6B : 0b-----11111-111--1---1-1--11-1-11
0x07DC8AD3 : 0b-----11111-111--1---1-1-11-1--11
0x07DC8B53 : 0b-----11111-111--1---1-11-1-1--11
0x07DC98AD : 0b-----11111-111--1--11---1-1-11-1
0x07DC98B5 : 0b-----11111-111--1--11---1-11-1-1
0x07DC9A2B : 0b-----11111-111--1--11-1---1-1-11
0x07DC9A8B : 0b-----11111-111--1--11-1-1---1-11
0x07DC9AC5 : 0b-----11111-111--1--11-1-11---1-1
0x07DCA26B : 0b-----11111-111--1-1---1--11-1-11
0x07DCA6B1 : 0b-----11111-111--1-1--11-1-11---1
0x07DCAC4D : 0b-----11111-111--1-1-11---1--11-1
0x07DCAD13 : 0b-----11111-111--1-1-11-1---1--11
0x07DCAD31 : 0b-----11111-111--1-1-11-1--11---1
0x07DCB135 : 0b-----11111-111--1-11---1--11-1-1
0x07DCB513 : 0b-----11111-111--1-11-1-1---1--11
0x07DCB531 : 0b-----11111-111--1-11-1-1--11---1
0x07DCC4AD : 0b-----11111-111--11---1--1-1-11-1
0x07DCC4B5 : 0b-----11111-111--11---1--1-11-1-1
0x07DCC569 : 0b-----11111-111--11---1-1-11-1--1
0x07DCC5A9 : 0b-----11111-111--11---1-11-1-1--1
0x07DCD12B : 0b-----11111-111--11-1---1--1-1-11
0x07DCD22B : 0b-----11111-111--11-1--1---1-1-11
0x07DCD2B1 : 0b-----11111-111--11-1--1-1-11---1
0x07DCD44B : 0b-----11111-111--11-1-1---1--1-11
0x07DCD48B : 0b-----11111-111--11-1-1--1---1-11
0x07DCD4B1 : 0b-----11111-111--11-1-1--1-11---1
0x07DCD625 : 0b-----11111-111--11-1-11---1--1-1
0x07DCD629 : 0b-----11111-111--11-1-11---1-1--1
▼6 <= 64 (зґенерив не всі, тільки кілька тисяч початкових і кінцевих, і тести вони пройшли)
Bits: 6, Length: 64, Count: 67108864
0x0218A392CD3D5DBF : 0b------1----11---1-1---111--1--1-11--11-1--1111-1-1-111-11-111111
0x0218A392CD3DBABF : 0b------1----11---1-1---111--1--1-11--11-1--1111-11-111-1-1-111111
0x0218A392CD3F576F : 0b------1----11---1-1---111--1--1-11--11-1--111111-1-1-111-11-1111
0x0218A392CD3F6EAF : 0b------1----11---1-1---111--1--1-11--11-1--111111-11-111-1-1-1111
0x0218A392CD5D3DBF : 0b------1----11---1-1---111--1--1-11--11-1-1-111-1--1111-11-111111
0x0218A392CD5D3F6F : 0b------1----11---1-1---111--1--1-11--11-1-1-111-1--111111-11-1111
0x0218A392CD5DBD3F : 0b------1----11---1-1---111--1--1-11--11-1-1-111-11-1111-1--111111
0x0218A392CD5DBF4F : 0b------1----11---1-1---111--1--1-11--11-1-1-111-11-111111-1--1111
0x0218A392CD5EDD3F : 0b------1----11---1-1---111--1--1-11--11-1-1-1111-11-111-1--111111
0x0218A392CD5FB74F : 0b------1----11---1-1---111--1--1-11--11-1-1-111111-11-111-1--1111
0x0218A392CDA7ABBF : 0b------1----11---1-1---111--1--1-11--11-11-1--1111-1-1-111-111111
0x0218A392CDA7BABF : 0b------1----11---1-1---111--1--1-11--11-11-1--1111-111-1-1-111111
0x0218A392CDA7EAEF : 0b------1----11---1-1---111--1--1-11--11-11-1--111111-1-1-111-1111
0x0218A392CDA7EEAF : 0b------1----11---1-1---111--1--1-11--11-11-1--111111-111-1-1-1111
0x0218A392CDABA7BF : 0b------1----11---1-1---111--1--1-11--11-11-1-1-111-1--1111-111111
0x0218A392CDABA7EF : 0b------1----11---1-1---111--1--1-11--11-11-1-1-111-1--111111-1111
0x0218A392CDABBD3F : 0b------1----11---1-1---111--1--1-11--11-11-1-1-111-1111-1--111111
0x0218A392CDABBF4F : 0b------1----11---1-1---111--1--1-11--11-11-1-1-111-111111-1--1111
0x0218A392CDABDD3F : 0b------1----11---1-1---111--1--1-11--11-11-1-1-1111-111-1--111111
0x0218A392CDABF74F : 0b------1----11---1-1---111--1--1-11--11-11-1-1-111111-111-1--1111
0x0218A392CDD3DABF : 0b------1----11---1-1---111--1--1-11--11-111-1--1111-11-1-1-111111
0x0218A392CDD3F6AF : 0b------1----11---1-1---111--1--1-11--11-111-1--111111-11-1-1-1111
0x0218A392CDD5ED3F : 0b------1----11---1-1---111--1--1-11--11-111-1-1-1111-11-1--111111
0x0218A392CDD5FB4F : 0b------1----11---1-1---111--1--1-11--11-111-1-1-111111-11-1--1111
0x0218A392CDDA7ABF : 0b------1----11---1-1---111--1--1-11--11-111-11-1--1111-1-1-111111
0x0218A392CDDA7EAF : 0b------1----11---1-1---111--1--1-11--11-111-11-1--111111-1-1-1111
0x0218A392CDDABD3F : 0b------1----11---1-1---111--1--1-11--11-111-11-1-1-1111-1--111111
0x0218A392CDDABF4F : 0b------1----11---1-1---111--1--1-11--11-111-11-1-1-111111-1--1111
0x0218A392CDEAED3F : 0b------1----11---1-1---111--1--1-11--11-1111-1-1-111-11-1--111111
0x0218A392CDED5D3F : 0b------1----11---1-1---111--1--1-11--11-1111-11-1-1-111-1--111111
0x0218A392CDFABB4F : 0b------1----11---1-1---111--1--1-11--11-111111-1-1-111-11-1--1111
0x0218A392CDFB574F : 0b------1----11---1-1---111--1--1-11--11-111111-11-1-1-111-1--1111
...
0x03D5DBF2CD271461 : 0b------1111-1-1-111-11-111111--1-11--11-1--1--111---1-1---11----1
...
0x03F6EAF2CD271461 : 0b------111111-11-111-1-1-1111--1-11--11-1--1--111---1-1---11----1
...
0x03F79D71B4A8B261 : 0b------111111-1111--111-1-111---11-11-1--1-1-1---1-11--1--11----1
0x03F79D71B4B09915 : 0b------111111-1111--111-1-111---11-11-1--1-11----1--11--1---1-1-1
0x03F79D71B4B0A899 : 0b------111111-1111--111-1-111---11-11-1--1-11----1-1-1---1--11--1
0x03F79D71B4B21513 : 0b------111111-1111--111-1-111---11-11-1--1-11--1----1-1-1---1--11
0x03F79D71B4B22615 : 0b------111111-1111--111-1-111---11-11-1--1-11--1---1--11----1-1-1
0x03F79D71B4B22A13 : 0b------111111-1111--111-1-111---11-11-1--1-11--1---1-1-1----1--11
0x03F79D71B4B26115 : 0b------111111-1111--111-1-111---11-11-1--1-11--1--11----1---1-1-1
0x03F79D71B4B26151 : 0b------111111-1111--111-1-111---11-11-1--1-11--1--11----1-1-1---1
0x03F79D71B4C22C95 : 0b------111111-1111--111-1-111---11-11-1--11----1---1-11--1--1-1-1
0x03F79D71B4C24595 : 0b------111111-1111--111-1-111---11-11-1--11----1--1---1-11--1-1-1
0x03F79D71B4C25459 : 0b------111111-1111--111-1-111---11-11-1--11----1--1-1-1---1-11--1
0x03F79D71B4C25915 : 0b------111111-1111--111-1-111---11-11-1--11----1--1-11--1---1-1-1
0x03F79D71B4C2A259 : 0b------111111-1111--111-1-111---11-11-1--11----1-1-1---1--1-11--1
0x03F79D71B4C2C895 : 0b------111111-1111--111-1-111---11-11-1--11----1-11--1---1--1-1-1
0x03F79D71B4C2C951 : 0b------111111-1111--111-1-111---11-11-1--11----1-11--1--1-1-1---1
0x03F79D71B4C2CA89 : 0b------111111-1111--111-1-111---11-11-1--11----1-11--1-1-1---1--1
0x03F79D71B4C84A8B : 0b------111111-1111--111-1-111---11-11-1--11--1----1--1-1-1---1-11
0x03F79D71B4C8544B : 0b------111111-1111--111-1-111---11-11-1--11--1----1-1-1---1--1-11
0x03F79D71B4C8950B : 0b------111111-1111--111-1-111---11-11-1--11--1---1--1-1-1----1-11
0x03F79D71B4C89615 : 0b------111111-1111--111-1-111---11-11-1--11--1---1--1-11----1-1-1
0x03F79D71B4C8A84B : 0b------111111-1111--111-1-111---11-11-1--11--1---1-1-1----1--1-11
0x03F79D71B4C8B095 : 0b------111111-1111--111-1-111---11-11-1--11--1---1-11----1--1-1-1
0x03F79D71B4C9508B : 0b------111111-1111--111-1-111---11-11-1--11--1--1-1-1----1---1-11
0x03F79D71B4C9510B : 0b------111111-1111--111-1-111---11-11-1--11--1--1-1-1---1----1-11
0x03F79D71B4C95161 : 0b------111111-1111--111-1-111---11-11-1--11--1--1-1-1---1-11----1
0x03F79D71B4C96115 : 0b------111111-1111--111-1-111---11-11-1--11--1--1-11----1---1-1-1
0x03F79D71B4C96151 : 0b------111111-1111--111-1-111---11-11-1--11--1--1-11----1-1-1---1
0x03F79D71B4CA848B : 0b------111111-1111--111-1-111---11-11-1--11--1-1-1----1--1---1-11
0x03F79D71B4CA890B : 0b------111111-1111--111-1-111---11-11-1--11--1-1-1---1--1----1-11
0x03F79D71B4CA8B09 : 0b------111111-1111--111-1-111---11-11-1--11--1-1-1---1-11----1--1
0x03F79D71B4CB0915 : 0b------111111-1111--111-1-111---11-11-1--11--1-11----1--1---1-1-1
0x03F79D71B4CB0A89 : 0b------111111-1111--111-1-111---11-11-1--11--1-11----1-1-1---1--1
Ці списки довелось вкоротити через обмеженя форуму. (це ok, вирізані куски не містили важливої інфо)
Ідея була така: Починайемо з 0, зразу додайемо це число в список використаних, далі це число зміщемо на 1 (v = (v << 1) | (b & 1);) і будемо пробувати дописувати 0 або 1 в молодший біт, рекурсивно.
0000
X \
0000 0001
/ \
0010 0011
/ | | \
0100 0101 0110 0111
/ | | | | | | \
1000 1001 1010 .. 1101 1110 1111
X X X | | X .. / | | | | X
... .. ...
Проблема в мойему алґоритмі або в реалізації (яку я покищо не хочу показувати, бо це просто сором), в малій швидкості, через це не вдайеться отримати всі значеня для 64 за прийнятний час (за годину, якщо писати в файл). І файл там буде великий, 0.5 GB, якщо в RAW тупо зкидувати всі числа (цикли біт, без дерева, без індексів).
Тому я шукаю в бітових циклах властивості, які дозволять зтворити інший ефективніший алґоритм, якщо він існує.
▼На даний момент маю виведено такі властивості
2^(2^(1-1)-1) = 1
2 == 2*(1)
1 // довжина послідовно однакових { 0 або 1 }
1 // кількість послідовних 0
1 // кількість послідовних 1
2^(2^(2-1)-2) = 1
4 == 2*(2)
2 // довжина послідовно однакових { 0 або 1 }
1 // кількість послідовних 0
1 // кількість послідовних 1
2^(2^(3-1)-3) = 2
8 == 2*(3 + 1*1)
3 1 // довжина послідовно однакових { 0 або 1 }
1 1 // кількість послідовних 0
1 1 // кількість послідовних 1
2^(2^(4-1)-4) = 16
16 == 2*(4 + 2*1 + 1*2)
4 2 1 // довжина послідовно однакових { 0 або 1 }
1 1 2 // кількість послідовних 0
1 1 2 // кількість послідовних 1
2^(2^(5-1)-5) = 2048
32 == 2*(5 + 3*1 + 2*2 + 1*4)
5 3 2 1 // довжина послідовно однакових { 0 або 1 }
1 1 2 4 // кількість послідовних 0
1 1 2 4 // кількість послідовних 1
2^(2^(6-1)-6) = 67108864
64 == 2*(6 + 4*1 + 3*2 + 2*4 + 1*8)
6 4 3 2 1 // довжина послідовно однакових { 0 або 1 }
1 1 2 4 8 // кількість послідовних 0
1 1 2 4 8 // кількість послідовних 1
2^(2^(7-1)-7) = 144115188075855872
128 == 2*(7 + 5*1 + 4*2 + 3*4 + 2*8 + 1*16)
7 5 4 3 2 1 // довжина послідовно однакових { 0 або 1 }
1 1 2 4 8 16 // кількість послідовних 0
1 1 2 4 8 16 // кількість послідовних 1
але якщо я почну їх користувати, то доведеться творити додаткові структури даних. Ймовірно час буде потратений, а вигода сумнівна..
Ідемо слідами предків.
.svg){kind=link}