title: c, obtaining a special random number
body: <p>I have a algorithm problem that I need to speed up :)</p>
  
  <p>I need a 32bit random number, with exact 10 bits set to 1. But in the same time, patterns like 101 (5 dec) and 11 (3 dec) to be considered illegal.</p>
  
  <p>Now the MCU is a 8051 (8 bit) and I tested all this in Keil uVision. My first attempt completes, giving the solution </p>
  
  <pre><code>0x48891249
  1001000100010010001001001001001   // correct, 10 bits 1, no 101 or 11
  </code></pre>
  
  <p>The problem is that it completes in 97 Seconds or 1165570706 CPU cycles which is ridiculous!!!</p>
  
  <p>Here is my code</p>
  
  <pre><code>// returns 1 if number is not good. ie. contains at leats one 101 bit sequence
  bool checkFive(unsigned long num)
  {
      unsigned char tmp;
  
      do {
  
              tmp = (unsigned char)num;
  
          if(
              (tmp &amp; 7) == 5 
          || (tmp &amp; 3) == 3
          ) // illegal pattern 11 or 101
                  return true; // found 
  
              num &gt;&gt;= 1;
      }while(num);
  
      return false;
  }
  
  void main(void) {
  
  
      unsigned long v,num; // count the number of bits set in v
      unsigned long c; // c accumulates the total bits set in v
  
      do {
              num = (unsigned long)rand() &lt;&lt; 16 | rand(); 
              v = num;
  
              // count all 1 bits, Kernigen style
              for (c = 0; v; c++)
                      v &amp;= v - 1; // clear the least significant bit set
  
      }while(c != 10 || checkFive(num));
  
    while(1);
  }
  </code></pre>
  
  <p>The big question for a brilliant mind :)
  Can be done faster? Seems that my approach is naive.</p>
  
  <p>Thank you in advance,</p>
  
  <p>Wow, I'm impressed, thanks all for suggestions. However, before accept, I need to test them these days.</p>
  
  <p>Now with the first option (look-up) it's just not realistic, will complete blow my 4K RAM of entire 8051 micro controller :) As you can see in image bellow, I tested for all combinations in Code Blocks but there are way more than 300 and it's not finished yet until 5000 index...</p>
  
  <p><a href="https://i.stack.imgur.com/S1SKg.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/S1SKg.jpg" alt="enter image description here"></a> </p>
  
  <p>The code I use to test</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdint.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdbool.h&gt;
  
  //#define bool  bit
  //#define   true    1
  //#define false 0
  
  
  
  // returns 1 if number is not good. ie. contains at leats one 101 bit sequence
  bool checkFive(uint32_t num)
  {
      uint8_t tmp;
  
      do {
  
              tmp = (unsigned char)num;
  
          if(
              (tmp &amp; 7) == 5
          || (tmp &amp; 3) == 3
          ) // illegal pattern 11 or 101
                  return true; // found
  
              num &gt;&gt;= 1;
      }while(num);
  
      return false;
  }
  
  void main(void) {
  
  
      uint32_t v,num; // count the number of bits set in v
      uint32_t c, count=0; // c accumulates the total bits set in v
  
      //printf("Program started \n");
  
      num = 0;
  
      printf("Program started \n");
  
      for(num=0; num &lt;= 0xFFFFFFFF; num++)
      {
  
  
          //do {
  
  
  
                  //num = (uint32_t)rand() &lt;&lt; 16 | rand();
                  v = num;
  
                  // count all 1 bits, Kernigen style
                  for (c = 0; v; c++)
                          v &amp;= v - 1; // clear the least significant bit set
  
          //}while(c != 10 || checkFive(num));
  
                  if(c != 10 || checkFive(num))
                      continue;
  
                  count++;
  
          printf("%d: %04X\n", count, num);
      }
  
      printf("Complete \n");
    while(1);
  }
  </code></pre>
  
  <p>Perhaps I can re-formulate the problem:</p>
  
  <p>I need a number with:</p>
  
  <ul>
  <li>precise (known) amount of 1 bits, 10 in my example</li>
  <li>not having 11 or 101 patterns</li>
  <li>remaining zeroes can be any</li>
  </ul>
  
  <p>So somehow, shuffle only the 1 bits inside.</p>
  
  <p>Or, take a 0x00000000 and add just 10 of 1 bits in random positions, except the illegal patterns.</p>