c# - 查找最左|最右位集的索引的高效按位运算

Question

在C++我可以使用编译器特定的内部函数来查找最左|最右位集，如this thread所示。

里面有没有类似的C#？或者我需要遍历所有位来实现这一点？

Answer 1

干得好。从这里改编的实现。

// Implementation of Least|Most SigBitSet from http://aggregate.org/MAGIC/

using System;

namespace Demo
{
    internal class Program
    {
        private static void Main()
        {
            int value = 0x0ff0; // 0000111111110000

            Console.WriteLine(LeastSigBitSet(value).ToString("x")); // 0x0010
            Console.WriteLine(MostSigBitSet(value).ToString("x"));  // 0x0800
        }

        public static int LeastSigBitSet(int value)
        {
            return (value & -value);
        }

        public static int MostSigBitSet(int value)
        {
            value |= (value >> 1);
            value |= (value >> 2);
            value |= (value >> 4);
            value |= (value >> 8);
            value |= (value >> 16);

            return (value & ~(value >> 1));
        }
    }
}

还有 unsigned int 版本（可能是您想要的版本）：

using System;

namespace Demo
{
    internal class Program
    {
        private static void Main()
        {
            uint value = 0x00ffff00; // 00000000111111111111111100000000

            Console.WriteLine(LeastSigBitSet(value).ToString("x")); // 0x0000100
            Console.WriteLine(MostSigBitSet(value).ToString("x"));  // 0x0800000
        }

        public static uint LeastSigBitSet(uint value)
        {
            return (value & 0u-value);
        }

        public static uint MostSigBitSet(uint value)
        {
            value |= (value >> 1);
            value |= (value >> 2);
            value |= (value >> 4);
            value |= (value >> 8);
            value |= (value >> 16);

            return (value & ~(value >> 1));
        }
    }
}

Answer 2

对于 ffs 之类的东西，无法访问特定于编译器的“内置”指令。您必须使用位掩码和移位操作等常规代码实现。但是，这并不一定意味着您需要遍历所有位：其中许多方法都有一些可怕的“常规”实现，疯狂地“添加一些不明显的奇异常量”，旨在删除大部分分支和迭代，这在 C# 中会非常好。如果您移植其中之一，要记住的主要事情是知道它是使用“有符号”还是“无符号”右移；如果它使用“签名”使用int（等）；如果它是“未签名的”，请使用uint（等）。

Answer 3

这里有很多人有复杂的解决方案......他说“高效”，所以如果他们能为你解决问题，我会选择这些。

lsb=i&-i;
msb=(int)(((double)i >> 20) - 1023);