Самый эффективный способ найти 1 в двоичном слове?

Question

Я не уверен, как это будет называться (отсюда и неуклюжее название), но мне нужно что-то подобное для чего-то, над чем я работаю. Я не могу описать это словами, но я надеюсь, что этот рисунок объяснит мне:

Каким был бы самый быстрый способ получения числа «в битах», «3» в этом примере, когда все после произвольного «индекса» (например, 5) следует игнорировать?

Answer 1

В дополнение к тому, что уже было сказано, я хотел бы обратить ваше внимание на то, что многие компиляторы предлагают встроенную функцию popcnt, которая может быть быстрее, чем делать это вручную (опять же, может быть, нет, не забудьте протестировать ее).).У них есть преимущество, вероятно, компиляции в один код операции popcnt, если он доступен в вашей целевой архитектуре (но я слышал, что они делают глупые медленные вещи, когда возвращаются к функции библиотеки), тогда как вам очень повезет, если компилятор обнаружит один изалгоритмы из коллекции битов Шона (но это возможно).

Для msvc это __ popcnt (и варианты), для gcc это __builtin_popcount (и варианты), для OpenCL (хорошо, что вы не сделали)не спрашивайте об этом, но почему бы не добавить его) это popcnt, но вы должны включить cl_amd_popcnt.

Answer 2

Сначала выполните input &= 0xfffffff8 (или эквивалент для вашего типа ввода), чтобы очистить три крайних правых бита. Тогда сделайте свой выбор отсюда .

Answer 3

Что-то вроде следующего:

int
countOnes( unsigned value, int top )
{
    assert( top >= 0 && opt < CHAR_BIT * sizeof( unsigned ) );
    value &= ~(~0 << top);
    int results = 0;
    while ( value != 0 ) {
        ++ results;
        value &= value - 1;
    }
    return results;
}

Это зависит от несколько неясного факта, что i & (i - 1) сбрасывает младший бит.

Answer 4

Таблица поиска даст вам эту информацию в постоянное время.