С учетом целого числа без знака, какой самый быстрый способ получить «индексы» установленных битов?

Question

Так, например, 0110 имеет биты 1 и 2, 1000 имеет бит 3, 1111 имеет биты 0,1,2,3

Answer 1

Если в действительности есть только 4 бита, то самый быстрый метод, безусловно, будет включать таблицу поиска. В конце концов, есть только 16 различных возможностей.

Answer 2

Лучший справочник в интернете для всех этих битовых хаков - битных хаддинговых хаков

Answer 3

for( int i = 0; variable ; ++i, variable >>= 1 ) {
  if( variable & 1 )
    // store bit index - i
}

Answer 4

Я бы сдвинул его вниз и проверил бы младший значащий бит в цикле. Это может быть более быстрое тестирование с 32-битными масками (или любой другой длины беззнакового целого).

/ Allan

Answer 5

Если бы это был .NET, и вам пришлось бы его часто использовать, я бы хотел хороший беглый интерфейс.

Я бы создал следующий класс (не совсем доволен именем BitTools).

[Flags]
public enum Int32Bits
{
    // Lookup table but nicer
    None = 0,
    Bit1 = 1,        Bit2  = 1 << 1,  Bit3  = 1 << 2,  Bit4  = 1 << 3,  Bit5  = 1 << 4,  Bit6  = 1 << 5,  Bit7  = 1 << 6,  Bit8  = 1 << 7,
    Bit9  = 1 << 8,  Bit10 = 1 << 9,  Bit11 = 1 << 10, Bit12 = 1 << 11, Bit13 = 1 << 12, Bit14 = 1 << 13, Bit15 = 1 << 14, Bit16 = 1 << 15,
    Bit17 = 1 << 16, Bit18 = 1 << 17, Bit19 = 1 << 18, Bit20 = 1 << 19, Bit21 = 1 << 20, Bit22 = 1 << 21, Bit23 = 1 << 22, Bit24 = 1 << 23,
    Bit25 = 1 << 24, Bit26 = 1 << 25, Bit27 = 1 << 26, Bit28 = 1 << 27, Bit29 = 1 << 28, Bit30 = 1 << 29, Bit31 = 1 << 30, Bit32 = 1 << 31,
}

public static class BitTools
{
    public static Boolean IsSet(Int32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }

    public static Boolean IsSet(UInt32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }

    public static Boolean IsBitSet(this Int32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }
    public static Boolean IsBitSet(this UInt32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }
}

И вы можете использовать его следующими способами:

static void Main(string[] args)
{
    UInt32 testValue =  5557; //1010110110101;

    if (BitTools.IsSet(testValue, Int32Bits.Bit1))
    {
        Console.WriteLine("The first bit is set!");
    }
    if (testValue.IsBitSet(Int32Bits.Bit5))
    {
        Console.WriteLine("The fifth bit is set!");
    }
    if (!testValue.IsBitSet(Int32Bits.Bit2))
    {
        Console.WriteLine("The second bit is NOT set!");
    }
}

Для каждого размера (U) Int вы можете создать другое перечисление Int * Bits и корректные перегрузки IsSet и IsBitSet.

РЕДАКТИРОВАТЬ: Я неправильно прочитал, вы говорите о неподписанных целых, но это то же самое в этом случае.

Answer 6

Я думаю, это поможет

import java.util.*;
public class bitSet {

    public static void main(String[]args) {
        Scanner scnr = new Scanner(System.in);
        int x = scnr.nextInt();
        int i = 0;
        while (i<32) {
            if ( ((x>>i)&1) == 1) {
                System.out.println(i);
            }
            i++;
        }
    }
}

Answer 7

Два шага:

1. Извлечь каждый установленный бит с помощью set_bit= x & -x; x&= x - 1;

2. Вычтите 1 и установите количество битов.

Answer 8

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

т.е. Предположим, вы начали с MSB 32-битного Int. Индексы верхнего полубайта я назову upper_idxs, а индексы нижнего полубайта я назову lower_idxs. Затем вам нужно добавить 24 к каждому элементу lower_idxs и добавить 28 к каждому элементу upper_idxs. Следующий байт будет обработан аналогичным образом, за исключением того, что смещения будут 16 и 20 соответственно, поскольку этот байт равен 8 битам "вниз".

Мне такой подход кажется разумным, но я был бы рад ошибиться: -)

Answer 9

@ Аллан Уинд ...

Дополнительные битовые сдвиги не нужны. Более эффективно не выполнять сдвиг битов, поскольку сравнение младшего значащего бита столь же эффективно, как сравнение второго младшего бита и т. Д. Сдвиг битов также удваивает необходимые битовые операции.

firstbit = (x & 0x00000001) 
secondbit = (x & 0x00000002) 
thirdbit = (x & 0x00000004)   //<-- I'm not saying to store these values, just giving an example. 
...

Все операции в системе x86 в любом случае выполняются с 32-разрядными регистрами, поэтому сравнение с одним битом будет столь же эффективным, как и 32-разрядное сравнение.

Не говоря уже о накладных расходах на наличие самого цикла.

Проблема может быть решена в постоянном количестве строк кода, и независимо от того, выполняется код на x86 или x64, способ, который я описываю, более эффективен.

Answer 10

Зависит от того, что вы подразумеваете под самым быстрым.

Если вы имеете в виду «просто кодировать», в .NET вы можете использовать класс BitArray и ссылаться на каждый бит как логическое значение true / false.

Класс BitArray