代码之家  ›  专栏  ›  技术社区  ›  Sijin

给定一个无符号整数,最快的方法是什么来获取集合位的“索引”?

  •  3
  • Sijin  · 技术社区  · 16 年前

    10 回复  |  直到 16 年前
        1
  •  7
  •   1800 INFORMATION    16 年前

    如果真的只有4位,那么最快的方法肯定需要一个查找表。毕竟只有16种不同的可能性。

        2
  •  6
  •   Philibert Perusse    16 年前

    比特黑客 - bit twiddling hacks

        3
  •  4
  •   Allan Wind    16 年前

    我将把它下移并测试循环中最低有效位。使用32位掩码(或无符号int的任何长度)进行测试可能会更快。

    /艾伦

        4
  •  4
  •   Mladen Janković    16 年前
    for( int i = 0; variable ; ++i, variable >>= 1 ) {
      if( variable & 1 )
        // store bit index - i
    }
    
        5
  •  1
  •   Davy Landman    16 年前

    如果它是.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 enum和正确的IsSet和IsBitSet重载。

    编辑:我误读了,你说的是无符号整数,但在这种情况下是一样的。

        6
  •  0
  •   Ash    16 年前

    取决于你所说的最快。

    如果您的意思是“易于编码”,那么在.NET中,您可以使用BitArray类并将每个位引用为布尔真/假。

    BitArray Class

        7
  •  0
  •   Brian R. Bondy    16 年前

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

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

    不管怎样,x86系统上的所有操作都是用32位寄存器完成的,因此单位比较和32位比较一样有效。

    更不用说循环本身的开销了。

        8
  •  0
  •   Peter Mortensen icecrime    14 年前

    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++;
            }
        }
    }
    
        9
  •  0
  •   Tim Cooper    13 年前

    i、 例如,假设您以32位int的MSB开始。上半字节索引我将调用上半字节idxs,下半字节索引我将调用下半字节idxs。然后你需要给下一个元素加24,给上一个元素加28。下一个字节将进行类似的处理,只是偏移量将分别为16和20,因为该字节是8位“down”。

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

        10
  •  0
  •   Tim Cooper    13 年前

    1. 提取每个集合位 set_bit= x & -x; x&= x - 1;

    2. 减去1并计算设置的位。