Подсчет количества битов, которые установлены

Question

Я хочу посчитать количество бит в двоичном числе, которые установлены. Например, пользователь вводит число 97, которое является 01100001 в двоичном виде. Программа должна дать мне, что 3 бита установлены с помощью MIPS ISA.

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

Есть идеи?

Заранее спасибо за помощь.

Это не HW, это крошечная часть моего исследовательского проекта.

Answer 1

То, что вы ищете, часто называют подсчетом населения (popcount).

Существует ряд реализаций C на Bit Twiddling Hacks (некоторые из которых страшныумная).Если вы знакомы с C, каждый подход должен иметь разумный перевод в сборку MIPS после разбивки выражений.

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

Answer 2

Поскольку это звучит как домашнее задание, я не собираюсь давать код MIPS, но вот алгоритм (написанный на C).Это должно быть легко перевести в MIPS:

int bits(unsigned int number)
{
    // clear the accumulator
    int accumulator = 0;
    // loop until our number is reduced to 0
    while (number != 0)
    {
        // add the LSB (rightmost bit) to our accumulator
        accumulator += number & 1;
        // shift the number one bit to the right so that a new
        // bit is in the LSB slot
        number >>= 1;
    }
    return accumulator;
}

Answer 3

Ссылка, которую дал Крис, дает несколько хороших методов подсчета битов. Я бы предложил этот метод , так как он очень быстрый и не требует зацикливания, а только побитовой операции, что было бы проще сделать при сборке.

Еще один способ получить код сборки - это создать код на C, скомпилировать его и затем посмотреть на выходную сборку (большинство компиляций может выводить файл сборки (-S для gcc, но обязательно отключите оптимизацию с помощью -O0, чтобы получить более легкий для понимания кода), или позволяет просматривать двоичный файл в разобранном виде). Это должно указать вам правильное направление.

Как анекдот, я некоторое время назад проводил тестирование на PowerPC (не MIPS, я знаю ...) для самого быстрого способа подсчета битов в 32-битном int. Метод, который я связал, был лучшим из всех других методов, пока я не сделал справочную таблицу размером в байт и обратился к ней 4 раза. Казалось бы, ALU медленнее, чем ссылка на кеш (работает около миллиона чисел по алгоритму).