title: Count integers in [1..N] with K zero bits below the leading 1? (popcount for a contiguous range without HW POPCNT)
body: <p>I have following task:
  Count how many numbers between 1 and N will have exactly K zero non-leading bits.  (e.g. 7<sub>10</sub>=111<sub>2</sub> will have 0 of them, 4 will have 2)</p>
  <p>N and K satisfy condition 0 ≤ K, N ≤ 1000000000</p>
  <p>This version uses POPCNT and is fast enough on my machine:</p>
  <pre><code>%include &quot;io.inc&quot;
  
  section .bss
      n resd 1
      k resd 1
      ans resd 1
  section .text
  global CMAIN
  CMAIN:
      GET_DEC 4,n
      GET_DEC 4,k
      mov ecx,1
      mov edx,0
      ;ecx is counter from 1 to n
  
  loop_:
      mov eax, ecx
      popcnt eax,eax;in eax now amount of bits set
      mov edx, 32
      sub edx, eax;in edx now 32-bits set=bits not set
      
      mov eax, ecx;count leading bits
      bsr eax, eax;
      xor eax, 0x1f;
      sub edx, eax
      mov eax, edx
      ; all this lines something like (gcc):
      ; eax=32-__builtin_clz(x)-_mm_popcnt_u32(x);
  
      cmp eax,[k];is there k non-leading bits in ecx?
      jnz notk
      ;if so, then increment ans
      
      mov edx,[ans]
      add edx,1
      mov [ans],edx
  notk:
      ;increment counter, compare to n and loop
      inc ecx
      cmp ecx,dword[n]
      jna loop_
      
      ;print ans
      PRINT_DEC 4,ans
      xor  eax, eax
      ret
  </code></pre>
  <p>It should be okay in terms of speed (~0.8 sec), but it wasn't accepted because (I guess) CPU used on testing server is too old so it shows that runtime error happened.</p>
  <p>I tried using precounting trick with a 64K * 4-byte lookup table, but it wasn't fast enough:</p>
  <pre><code>%include &quot;io.inc&quot;
  section .bss
      n resd 1
      k resd 1
      ans resd 1
      wordbits resd 65536; bits set in numbers from 0 to 65536
  section .text
  global CMAIN
  CMAIN:
      mov ebp, esp; for correct debugging
      mov ecx,0
      ;mov eax, ecx
      ;fill in wordbits, ecx is wordbits array index
  precount_:
      mov eax,ecx
      xor ebx,ebx
      ;c is ebx, v is eax
      ;for (c = 0; v; c++){
      ;    v &amp;= v - 1; // clear the least significant bit set
      ;}
  lloop_:
      mov edx,eax
      dec edx
      and eax,edx
      inc ebx
      test eax,eax
      jnz lloop_
      
      ;computed bits set
      mov dword[wordbits+4*ecx],ebx
      
      inc ecx
      cmp ecx,65536
      jna precount_
      
      ;0'th element should be 0
      mov dword[wordbits],0
      
      GET_DEC 4,edi;n
      GET_DEC 4,esi;k
      
      mov ecx,1
      xor edx,edx
      xor ebp,ebp
      
  loop_:
      mov eax, ecx
      ;popcnt eax,eax
      mov edx,ecx
      and eax,0xFFFF 
      shr edx,16
      mov eax,dword[wordbits+4*eax]
      add eax,dword[wordbits+4*edx]
      ;previous lines are to implement absent instruction popcnt.
      ; they simply do eax=wordbits[x &amp; 0xFFFF] + wordbits[x &gt;&gt; 16]
      mov edx, 32
      sub edx, eax
      ;and the same as before: 
      ;non-leading zero bits=32-bits set-__builtin_clz(x)
      mov eax, ecx
      bsr eax, eax
      xor eax, 0x1f
      sub edx, eax
      mov eax, edx
  
      ;compare to k again to see if this number has exactly k 
      ;non-leading zero bits
  
      cmp edx, esi
      jnz notk
  
      ;increment ebp (answer) if so
      mov edx, ebp
      add edx, 1
      mov ebp, edx
      ;and (or) go to then next iteration 
  notk:
      inc ecx
      cmp ecx, edi
      jna loop_
      
      ;print answer what is in ebp
      PRINT_DEC 4, ebp
      xor  eax, eax
      ret
  </code></pre>
  <p>(&gt;1 sec)</p>
  <p>Should I speed up second program (if so, then how?) or somehow replace POPCNT with some other (which?) instructions (I guess SSE2 and older should be available)?</p>