Блог

Главная - Вопросы по программированию - Как посчитать 0 ИЛИ 1 в двоичном числе, не зная, какое из них заранее

Как посчитать 0 ИЛИ 1 в двоичном числе, не зная, какое из них заранее

#assembly #mips #bitmask

#сборка #mips #битовая маска

Вопрос:

Я работаю в сборке (MIPS32), и мне нужно подсчитать количество 0 ИЛИ 1 на основе решения пользователя. (т. Е. Я не знаю, что заранее)

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

Пример1:

двоичное воспроизведение числа: 00001010

выбор пользователя: 0

ответ: 6

Пример2:

двоичное воспроизведение числа: 00001010

выбор пользователя: 1

ответ: 2

Я понимаю, как использовать битовую маску для подсчета общего количества, если я знаю, какой из них заранее. Тем не менее, я полностью запутался в том, как подойти к получению количества либо без знания того, что заранее.

Ответ №1:

Итак, допустим, вы знаете, как подсчитать количество 0. Один из подходов заключается в том, что, если пользователь хочет получить 1, вы дополняете (НЕ побитово) число перед подсчетом 0.

Одним из способов достижения последнего является XOR с -1 (в представлении дополнения two, так что все это 1s). Если вы отрицаете выбор пользователем 0 или 1, вы получаете 0 или -1, а XOR с 0 не влияет на число. Итак, в C это может выглядеть так

result = count_zeros(number ^ -choice)

Я не знаю набора инструкций MIPS, поэтому я оставлю это вам, чтобы написать это в сборке.

(Если это для задания, не забудьте указать этот ответ в своем сообщении.)

Комментарии:

1. Или вы можете выполнить работу заранее ones_count = popcount(number) , а затем после выбора пользователя делать 32-ones_count или нет.

2. @PeterCordes: Я рассматривал это, но не так удобно делать это без ветвей, как того требует OP.

3.О да, я пропустил, что это требование. Существует трюк для 31-count для count 0 ..31: count ^= 31 , который вы могли бы сделать без ветвей, но все же менее удобно. (GCC использует этот трюк, чтобы перевести bsr результаты x86 в clz). Но это не помогает 32-count . Конечно, MIPS4 и более поздние версии имеют movz / movn условное перемещение на основе другого регистра, равного 0 или отличного от нуля, что упрощает задачу. clang компилирует без ветвлений для return ones ? x : 32-x; godbolt.org/z/ThTMMc . Но да, если вы не оптимизируете задержку от единиц до результата, тогда ваш способ хорош и прост.