c# - 左端または右端のビット セットのインデックスを見つけるための効率的なビット演算

Question

このスレッドC++に示されているように、コンパイラ固有の intrisics を使用して、左端|右端のビット セットを見つけることができます。

に似たようなものはありC#ますか? または、それを達成するためにすべてのビットを反復処理する必要がありますか?

Answer 1

どうぞ。here から適応された実装。

// 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(etc) を使用します。