给定一个无符号整数，得到设定位“索引”的最快方法是什么？

答

我将它向下移动并测试循环中的最低有效位。用32位掩码（或者你的无符号整数是任意长度）可能会更快。

/艾伦

+0

打我。而你的解决方案很好。 – owenmarshall 2008-09-16 02:46:03

+0

我不确定为什么每个人都认为比较LSB是一个非常快速的操作相比，比较其他位... – 2008-09-16 03:05:25

答

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

答

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

如果你的意思是“简单代码”，你可以在.NET中使用BitArray类，并将每一位引用为布尔真/假。

BitArray Class

答

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

答

@Allan风...

不需要额外的位移位。不进行位移是更有效的，因为比较最低有效位与比较第二最低有效位等效率一样。做一点点改变也只是将所需的位操作加倍。

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

答

在互联网上

最佳参照，所有这些位黑客 - bit twiddling hacks

答

您可以通过INT的字节迭代的混合方法，使用查找表来确定一组比特的索引每个字节（分解为半字节）。然后，您需要向索引添加一个偏移量以反映其在整数中的位置。

即假设你以32位整数的MSB开始。我将调用upper_idxs的较高半字节索引，以及我将调用lower_idxs的较低半字节索引。然后，您需要将24添加到lower_idxs的每个元素，并将28添加到upper_idxs的每个元素。下一个字节将被类似地处理，除了偏移将分别是16和20，因为该字节是8位“向下”。

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

答

如果是.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）中等大小，你可以再拍诠释*位枚举和IsSet和IsBitSet的正确重载。

编辑：我误读了，你说的是未签名的整数，但在这种情况下是一样的。

答

两个步骤：

提取每一组位设置set_bit= x & -x; x&= x - 1;
减去1和计数比特。

答

我认为这将有助于

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++; 
     } 
    } 
}

给定一个无符号整数，得到设定位“索引”的最快方法是什么？

相关推荐