3

因此，例如 0110 设置了位 1 和 2，1000 设置了位 3 1111 设置了位 0、1、2、3

4

10 回答 10

7

如果真的只有 4 位，那么最快的方法肯定是使用查找表。毕竟只有 16 种不同的可能性。

于 2008-09-16T02:51:53.370 回答
6

互联网上所有这些小技巧的最佳参考-小技巧

于 2008-09-16T03:15:16.730 回答
4

我会将它向下移动并测试循环中的最低有效位。使用 32 位掩码（或 unsigned int 的任何长度）进行测试可能会更快。

/艾伦

于 2008-09-16T02:42:17.353 回答
4 
for( int i = 0; variable ; ++i, variable >>= 1 ) {
  if( variable & 1 )
    // store bit index - i
}
于 2008-09-16T02:48:34.640 回答
1

If it was .NET and you'd have to use it a lot I would like a nice fluent interface.

I would create the following class (not totally happy with the name 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;
    }
}

And you could use it the following ways:

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!");
    }
}

For each (U)Int size you could make another Int*Bits enum and the correct overloads of IsSet and IsBitSet.

EDIT: I misread, you're talking about unsigned ints, but it's the same in this case.

于 2008-09-16T13:39:51.627 回答
0

取决于你所说的最快是什么意思。

如果您的意思是“代码简单”，那么在 .NET 中，您可以使用 BitArray 类并将每个位称为布尔值 true/false。

位数组类

于 2008-09-16T02:50:16.447 回答
0

@艾伦风...

不需要额外的位移。不进行位移更有效，因为比较最低有效位与比较第二个最低有效位一样有效，依此类推。进行位移也只是将所需的位操作加倍。

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 上运行，我描述的方式更有效。

于 2008-09-16T03:02:16.400 回答
0

您可以采用迭代 int 字节的混合方法，使用查找表来确定每个字节中设置位的索引（分成半字节）。然后您需要向索引添加偏移量以反映其在整数中的位置。

即假设您从 32 位 int 的 MSB 开始。我将上半字节索引称为upper_idxs，而将下半字节索引称为lower_idxs。然后需要给lower_idxs的每个元素加24，给upper_idxs的每个元素加28。下一个字节将被类似地处理，除了偏移量将分别为 16 和 20，因为该字节是 8 位“向下”。

对我来说，这种方法似乎是合理的，但我很乐意证明是错误的 :-)

于 2008-09-16T06:57:35.587 回答
0

两步：

  1. 提取每个设置位set_bit= x & -x; x&= x - 1;

  2. 减 1 并计数设置的位数。

于 2008-09-16T23:34:11.183 回答
0

我认为这会有所帮助

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++;
        }
    }
}
于 2010-06-21T07:55:00.143 回答