高效的按位操作，查找最左/最右位集的索引

本文关键字：索引 位操作 查找 高效 | 更新日期: 2023-09-27 17:54:57

在C++中，我可以使用编译器特定的特性来查找左|右最位集，如本线程所示。

在C#中是否有类似的情况?或者我需要遍历所有的位来实现它?

高效的按位操作，查找最左/最右位集的索引

给你。

// 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));
        }
    }
}

无法访问诸如ffs之类的编译器特定的"内置"指令。你必须使用像位掩码和移位操作这样的常规代码实现。然而，这并不一定意味着你需要迭代所有的比特:对于这些方法中的许多都有一些非常聪明的"常规"实现，做一些疯狂的"添加一些不明显的奇怪常量"，旨在减少大部分分支和迭代，这在c#中是完全没问题的。如果你移植了其中一个，要记住的主要事情是知道它是使用"有符号"还是"无符号"右移;如果使用"signed"，则使用int(等);如果是"unsigned"，则使用uint(等)。

可以使用BitOperations.LeadingZeroCount()和BitOperations.TrailingZeroCount()。

很多人都有复杂的解决方案…他说"高效"，所以如果它们对你有用的话，我就买这些。

lsb=i&-i;
msb=(int)(((double)i >> 20) - 1023);
相关文章：