NASM: подсчитайте, сколько битов в 32-битном числе установлено в 1 - PullRequest
Новая
       30

NASM: подсчитайте, сколько битов в 32-битном числе установлено в 1

4 голосов
/ 28 мая 2010

У меня есть 32-битное число, и я хочу подсчитать, знать, сколько битов 1.

Я думаю об этом псевдокоде: 

mov eax, [number]
while(eax != 0)
{
  div eax, 2
  if(edx == 1)
  {
   ecx++;
  } 
  shr eax, 1
}

Есть ли более эффективный способ?

Я использую NASM на процессоре x86.

(Я только начинаю с ассемблера, поэтому, пожалуйста, не говорите мне использовать код из библиотек extern, потому что я даже не знаю, как их включить;))

(Я только что нашел Как посчитать количество установленных бит в 32-разрядном целом числе? , которое также содержит мое решение. Есть другие опубликованные решения, но, к сожалению, я не могу понять как бы я их написал на ассемблере)

Ответы [ 6 ]

7 голосов
/ 28 мая 2010

Самый эффективный способ (с точки зрения времени выполнения, во всяком случае) - это иметь справочную таблицу. Очевидно, что у вас не будет таблицы с 4 миллиардами записей, но вы можете разбить 32 бита на 8-битные порции, и вам понадобится только таблица с 256 входами, или далее, на 4-битные порции, и потребуется всего 16 записей. , Удачи!

6 голосов
/ 28 мая 2010

В процессорах с поддержкой SSE4 у вас есть инструкция POPCNT, которая делает это за вас.

Самый наивный алгоритм на самом деле быстрее, чем вы думали (инструкции DIV очень медленные). 

mov eax, [number]
xor ecx,ecx
loop_start:
  test eax,1
  jnz next
  inc ecx
next:
  shr eax, 1
  mov eax,ecx

Что касается вашего комментария о предыдущих SO-ответах, я возьму пример ответа оттуда и расскажу, как его преобразовать. 

long count_bits(long n) {     
  unsigned int c; // c accumulates the total bits set in v
  for (c = 0; n; c++) 
    n &= n - 1; // clear the least significant bit set
  return c;
}

(Я предполагаю, что вы знаете, как определить функцию и тому подобное). Необходим очень простой цикл, переменная счетчика (традиционно ecx - это и индекс, и счетчик) и инструкции по тестированию битов. 

    mov edx,n
    xor ecx,ecx
loop_start:
    test edx,edx
    jz end
    mov ebx,edx
    dec ebx
    and edx,ebx
    inc ecx
    jmp loop_start
end:
    mov eax,ecx
    ret

Реализация чего-то подобного алгоритму веса Хэмминга в сборке не сложна, но просто достаточно сложна, чтобы вы не хотели делать это как начальную домашнюю задачу.

4 голосов
/ 28 мая 2010

Мой x86 ассемблер немного ржавый, но это приходит на ум: 

clc            ; clear carry
xor ecx, ecx   ; clear ecx

shl eax, 1     ; shift off one bit into carry
adc ecx, 0     ; add carry flag to ecx
; ... repeat the last two opcodes 31 more times

ecx содержит ваш счетчик битов.

инструкции по сдвигу x86 setCF до последнего сдвинутого бита, где adc ecx, 0 читает его.

1 голос
/ 06 августа 2017 
      mov eax,[c]
      xor ebx,ebx
SSS:  shr eax,1    ; after shift, if eax=0 ZF flag=1
      jz  XXX      ; end (no more bit on eax)
      adc bl
      jmp SSS
XXX:  adc bl
      movb [Nbit],bl
0 голосов
/ 18 февраля 2018

Использование bsf (Bit Scan Forward), вероятно, немного более эффективно, чем простое смещение. 

xor         edx,edx  
mov         eax,num  
bsf         ecx,eax
je          end_bit_count
; align?
loop_bit_count:
inc         ecx  
inc         edx  
shr         eax,cl  
bsf         ecx,eax  
jne         loop_bit_count
end_bit_count:
0 голосов
/ 11 мая 2016

Эта программа выдает количество единиц в 32-битном числе. Попробуйте :) 

extern printf                     
SECTION .data                   
msg:    db "The number of 1 bits are: %d",10,0
inta1:  dd  1234567  
num: dd  2147483647   
SECTION .text                     

global  main                  
main:     
    mov eax, [num]  
    mov ecx,32  
    mov edx,0  
.loop:  dec ecx  
    cmp ecx,0  
    jl .exit  
    shr eax,1  
    jnc .loop  
    inc edx  
jmp .loop 
.exit:
    push edx
    push    dword msg         
    call    printf            
    add     esp, 8
...