Наименьший цикл размера кода для подсчета битов в регистре (уменьшение другого регистра)?

Question

Мне нужно написать следующий фрагмент кода C в сборке 8086* как можно короче (менее 10 байт), но мне удается записать его только в 12 байт.

есть идеи?

while (ax) {
    bx--;
    ax &= ax-1;
}

Answer 1

Операция, которую вы пытаетесь назвать, называется счетчиком чисел, то есть подсчитывает количество установленных битов в регистре.

На самом деле для более новых процессоров есть отдельная инструкция. А так как ориентация на оригинальный 8086 действительно не так интересна в 2018 году.

Простой ответ:

f3 0f b8 c0             popcnt eax,eax
29 c3                   sub    ebx,eax 

6 байтов, которые можно уменьшить до 4, если вы хотите разрешить положительное значение в ebx и может предположить / убедиться, что ebx равен нулю для начала.

Обратите внимание, что нет необходимости работать с 16-битными регистрами, не было уже много лет.

Если вы хотите, чтобы код работал на оригинальном 8086 (который не поддерживает popcnt) вам придется сохранить цикл.

Следующий совершенно простой код занимает 12 байтов:

85 c0                   test   ax,ax          ;is AX zero?
74 08                   je     <done>         ;yes, bail out
<loop>:
4b                      dec    bx             ;bx--
89 c1                   mov    cx,ax
49                      dec    cx             ;cx = ax - 1
21 c8                   and    ax,cx          ;ax = ax & (ax-1) 
75 f8                   jne    <loop>         ;repeat until done
<done>:

Вы можете сократить это до 9 байтов, считая биты немного менее эффективным способом. Здесь мы просто тестируем все 16 бит топора.

<loop>:
d1 e0                   shl    ax,1       ;MSb to carry flag (CF)
83 db 00                sbb    bx,0       ;bx=bx-CF
85 c0                   test   ax,ax      ;is AX zero?
75 f9                   jnz    <loop>     ;if not then loop until done

Хитрость заключается в том, чтобы понять, что делает код, а затем перефразировать его по-другому.