4 ms·
De Bruijn sequences can also be used to quickly find the index of 1 in a word, when your CPU doesn't provide a dedicated instruction like lzcnt[1] (or when you'
by GrumpySloth 4y ago
De Bruijn sequences can also be used to quickly find the index of 1 in a word, when your CPU doesn't provide a dedicated instruction like lzcnt[1] (or when you're in a language competition which doesn't allow writing inline assembly). The paper talks only about 32-bit words, but you may find a 64-bits long de Bruijn sequence (B(2, 6)) on the Chessprogramming Wiki[2], which allows you to trivially generalise the algorithm for 64-bit words.
[1]: <https://www.researchgate.net/publication/2809440_Using_de_Bruijn_Sequences_to_Index_a_1_in_a_Computer_Word https://www.researchgate.net/publication/2809440_Using_de_Br...>
[2]: <https://www.chessprogramming.org/index.php?title=De_Bruijn_Sequence&mobileaction=toggle_view_mobile https://www.chessprogramming.org/index.php?title=De_Bruijn_S...>
- bombcar 4y agoThey can also be used to unlock Fords: https://hackaday.com/2018/06/18/opening-a-ford-with-a-robot-and-the-de-bruijn-sequence/ https://hackaday.com/2018/06/18/opening-a-ford-with-a-robot-... Because the computer just checks if the "last n digits are correct" so you don't need to restart each time. Garage door openers are susceptible to it, also.