Compiler Explorer

Source code

%if 0    ;; Perf counter results on i7-6700k at 3.9GHz
$ nasm -felf32 foo.asm && gcc -m32 -no-pie -fno-pie -fno-plt foo.o
$ taskset -c 3 perf stat -B --all-user -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 1 ./a.out 
ans: 12509316

Performance counter stats for './a.out':

536.49 msec task-clock                #    0.999 CPUs utilized          
                 0      context-switches          #    0.000 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
                44      page-faults               #    0.082 K/sec                  
     2,089,479,797      cycles                    #    3.895 GHz                    
     2,012,556,778      branches                  # 3751.376 M/sec                  
         2,047,286      branch-misses             #    0.10% of all branches        
     9,025,236,489      instructions              #    4.32  insn per cycle         
     7,133,922,940      uops_issued.any           # 13297.525 M/sec                 
     6,084,088,670      uops_executed.thread      # 11340.650 M/sec

0.536929691 seconds time elapsed

0.536516000 seconds user
       0.000000000 seconds sys
%endif

%use SMARTALIGN
alignmode p6, 64

section .bss
;    n resd 1
;    k resd 1
    ans resd 1
section .rodata
  n: dd 1000000000
  k: dd 8
  print_fmt: db `ans: %d\n`, 0

section .text
global main
main:
    push  esi
    push  ebx
;    GET_DEC 4,n
;    GET_DEC 4,k
    mov   ecx, [n]      ; ecx counts from n down to 1
    mov   esi, [k]
    xor   ebx, ebx      ; ebx = ans

align 32
.loop:
    mov    eax, ecx
    popcnt eax,eax
    lea    edx, [dword eax - 32 + 31]  ; popcnt - 32  =  -(bits not set)
                   ; dword displacement pads the cmp/jnz location to avoid the JCC erratum penalty on Intel

;    xor eax, eax         ; break false dependency, or just let OoO exec hide it after breaking once per iter
    bsr eax, ecx         ; eax = 31-lzcnt
;    xor eax, 0x1f        ; eax = lzcnt (for non-zero x)
    ; want:  32-__builtin_clz(x)-_mm_popcnt_u32(x)  = (31-clz) + 1-popcnt = (31-clz) - (popcnt-1)
    sub eax, edx

cmp eax, esi  ;is there k non-leading bits in ecx?
%if 0
    jnz .notk
    inc ebx       ;if so, then increment ans
.notk:
%else
    jz .yesk      ; not-taken is the more common fast path
 .done_inc:
%endif
    dec ecx
    jnz .loop   ; }while(--n >= 0U)
    
    ;print ans
;    PRINT_DEC 4,ans
    push  ebx
    push  print_fmt
extern printf
    call  printf
    add   esp, 8

pop  ebx
    pop  esi
    xor  eax, eax
    ret

.yesk:
   inc  ebx
   jmp  .done_inc