Hacker News new | ask | show | jobs
by GrumpySloth 1456 days 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_Br...>

[2]: <https://www.chessprogramming.org/index.php?title=De_Bruijn_S...>

1 comments

They can also be used to unlock Fords: 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.