Editing De Bruijn sequence (section)

== Uses ==
de Bruijn cycles are of general use in neuroscience and psychology experiments that examine the effect of stimulus order upon neural systems,{{sfnp|Aguirre|Mattar|Magis-Weinberg|2011}} and can be specially crafted for use with [[functional magnetic resonance imaging]].<ref>{{cite web |url=https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn_software |title=de Bruijn cycle generator |access-date=2015-09-15 |archive-date=2016-01-26 |archive-url=https://web.archive.org/web/20160126133108/https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn_software |url-status=dead }}</ref>

===Angle detection===
The symbols of a de Bruijn sequence written around a circular object (such as a wheel of a [[robot]]) can be used to identify its [[angle]] by examining the ''n'' consecutive symbols facing a fixed point. This angle-encoding problem is known as the "rotating drum problem".{{sfnp|van Lint|Wilson|2001}} [[Gray code]]s can be used as similar rotary positional encoding mechanisms, a method commonly found in [[rotary encoder]]s.

===Finding least- or most-significant set bit in a word===
A de Bruijn sequence can be used to quickly find the index of the least significant set bit ("right-most 1") or the most significant set bit ("left-most 1") in a [[Word (data type)|word]] using [[bitwise operation]]s and multiplication.<ref>{{harvtxt|Anderson|1997–2009}}; {{harvtxt|Busch|2009}}</ref> The following example uses a de Bruijn sequence to determine the index of the least significant set bit (equivalent to counting the number of trailing '0' bits) in a 32 bit unsigned integer:

<syntaxhighlight lang="cpp">
uint8_t lowestBitIndex(uint32_t v)
{       
  static const uint8_t BitPositionLookup[32] = // hash table
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return BitPositionLookup[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
}
</syntaxhighlight>

The <code>lowestBitIndex()</code> function returns the index of the least-significant set bit in ''v'', or zero if ''v'' has no set bits. The constant 0x077CB531U in the expression is the ''B''&thinsp;(2,&nbsp;5) sequence 0000&thinsp;0111&thinsp;0111&thinsp;1100&thinsp;1011&thinsp;0101&thinsp;0011&thinsp;0001 (spaces added for clarity). The operation <code>(v & -v)</code> zeros all bits except the least-significant bit set, resulting in a new value which is a power of 2. This power of 2 is multiplied (arithmetic modulo 2<sup>32</sup>) by the de Bruijn sequence, thus producing a 32-bit product in which the bit sequence of the 5 MSBs is unique for each power of 2. The 5 MSBs are shifted into the LSB positions to produce a hash code in the range [0, 31], which is then used as an index into [[hash table]] BitPositionLookup. The selected hash table value is the bit index of the least significant set bit in ''v''.

The following example determines the index of the most significant bit set in a 32 bit unsigned integer:

<syntaxhighlight lang="cpp">
uint32_t keepHighestBit(uint32_t n)
{
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

uint8_t highestBitIndex(uint32_t v)
{
    static const uint8_t BitPositionLookup[32] = { // hash table
         0,  1, 16,  2, 29, 17,  3, 22, 30, 20, 18, 11, 13,  4,  7, 23,
        31, 15, 28, 21, 19, 10, 12,  6, 14, 27,  9,  5, 26,  8, 25, 24,
    };
    return BitPositionLookup[(keepHighestBit(v) * 0x06EB14F9U) >> 27];
}
</syntaxhighlight>

In the above example an alternative de Bruijn sequence (0x06EB14F9U) is used, with corresponding reordering of array values. The choice of this particular de Bruijn sequence is arbitrary, but the hash table values must be ordered to match the chosen de Bruijn sequence. The <code>keepHighestBit()</code> function zeros all bits except the most-significant set bit, resulting in a value which is a power of 2, which is then processed as in the previous example.

===Brute-force attacks on locks===

[[File:De_Bruijn_sequence_10_4.svg|thumb|One possible ''B''&thinsp;(10,&nbsp;4) sequence. The 2530 substrings are read from top to bottom then left to right, and their digits are concatenated. To get the string to brute-force a combination lock, the last three digits in brackets (000) are appended. The 10003-digit string is hence "0 0001 0002 0003 0004 0005 0006 0007 0008 0009 0011 ... 79 7988 7989 7998 7999 8 8889 8899 89 8999 9 000" (spaces added for readability).]]
{| class="infobox wikitable collapsible collapsed" style="text-align:center;font-size:80%;line-height:0.5;"
|- style="text-align:left;font-size:125%;line-height:1;"
|colspan="10"|B{10,3} with digits read from top to bottom<br />then left to right;<ref>{{Cite web|url=http://hakank.org/comb/debruijn.cgi?k=10&n=3|title = de Bruijn (DeBruijn) sequence (K=10, n=3)}}</ref> appending "00" yields<br />a string to brute-force a 3-digit combination lock
|- style="vertical-align:top;"
|0
|rowspan="12"|1
|rowspan="23"|2
|rowspan="34"|3
|rowspan="45"|4
|rowspan="56"|5
|rowspan="67"|6
|rowspan="78"|7
|rowspan="89"|8
|rowspan="99"|9
|-
|001
|-
|002
|-
|003
|-
|004
|-
|005
|-
|006
|-
|007
|-
|008
|-
|009
|-
| 
|-
|011
|-
|012||112
|-
|013||113
|-
|014||114
|-
|015||115
|-
|016||116
|-
|017||117
|-
|018||118
|-
|019||119
|-
| 
|-
|021
|-
|022||122
|-
|023||123||223
|-
|024||124||224
|-
|025||125||225
|-
|026||126||226
|-
|027||127||227
|-
|028||128||228
|-
|029||129||229
|-
| ||rowspan="2"|
|-
|031
|-
|032||132
|-
|033||133||233
|-
|034||134||234||334
|-
|035||135||235||335
|-
|036||136||236||336
|-
|037||137||237||337
|-
|038||138||238||338
|-
|039||139||239||339
|-
| ||rowspan="2"| ||rowspan="3"|
|-
|041
|-
|042||142
|-
|043||143||243
|-
|044||144||244||344
|-
|045||145||245||345||445
|-
|046||146||246||346||446
|-
|047||147||247||347||447
|-
|048||148||248||348||448
|-
|049||149||249||349||449
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"|
|-
|051
|-
|052||152
|-
|053||153||253
|-
|054||154||254||354
|-
|055||155||255||355||455
|-
|056||156||256||356||456||556
|-
|057||157||257||357||457||557
|-
|058||158||258||358||458||558
|-
|059||159||259||359||459||559
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"|
|-
|061
|-
|062||162
|-
|063||163||263
|-
|064||164||264||364
|-
|065||165||265||365||465
|-
|066||166||266||366||466||566
|-
|067||167||267||367||467||567||667
|-
|068||168||268||368||468||568||668
|-
|069||169||269||369||469||569||669
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"| ||rowspan="6"|
|-
|071
|-
|072||172
|-
|073||173||273
|-
|074||174||274||374
|-
|075||175||275||375||475
|-
|076||176||276||376||476||576
|-
|077||177||277||377||477||577||677
|-
|078||178||278||378||478||578||678||778
|-
|079||179||279||379||479||579||679||779
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"| ||rowspan="6"| ||rowspan="7"|
|-
|081
|-
|082||182
|-
|083||183||283
|-
|084||184||284||384
|-
|085||185||285||385||485
|-
|086||186||286||386||486||586
|-
|087||187||287||387||487||587||687
|-
|088||188||288||388||488||588||688||788
|-
|089||189||289||389||489||589||689||789||889
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"| ||rowspan="6"| ||rowspan="7"| ||rowspan="8"|
|-
|091
|-
|092||192
|-
|093||193||293
|-
|094||194||294||394
|-
|095||195||295||395||495
|-
|096||196||296||396||496||596
|-
|097||197||297||397||497||597||697
|-
|098||198||298||398||498||598||698||798
|-
|099||199||299||399||499||599||699||799||899||(00)
|}
A de Bruijn sequence can be used to shorten a brute-force attack on a [[Personal Identification Number|PIN]]-like code lock that does not have an "enter" key and accepts the last ''n'' digits entered. For example, a [[digital door lock]] with a 4-digit code (each digit having 10 possibilities, from 0 to 9) would have ''B''&thinsp;(10,&nbsp;4) solutions, with length {{val|10000}}. Therefore, only at most {{nowrap|{{val|10000}} + 3 {{=}} {{val|10003}}}} (as the solutions are cyclic) presses are needed to open the lock, whereas trying all codes separately would require {{nowrap|4 × {{val|10000}} {{=}} {{val|40000}}}} presses.

{{Anoto_paper_principle.svg}}