CODEWITHSUNDEEP
c#bit-manipulationperformance
Heisenbug
Heisenbug

Reputation: 39164

Efficient bitwise operation to find the index of the left|right most bit set

In C++ I can use compiler specific intrisics to find the left|right most bit set, like shown in this thread.

Is there anything similar in C#? Or I need to iterate over all the bits to achieve that?

Upvotes: 1

Views: 2429

Answers (4)

M.Toy
M.Toy

Reputation: 103

You can use BitOperations.LeadingZeroCount() and BitOperations.TrailingZeroCount(). They use hardware intrinsics when available.

Upvotes: 2

Chris Roberts
Chris Roberts

Reputation: 11

Lots of people with complicated solutions here... He said "efficient", so I'd go with these if they'll do the trick for you.

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

Upvotes: 0

Matthew Watson
Matthew Watson

Reputation: 109547

Here you go. Implementations adapted from 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));
        }
    }
}

And the unsigned int version (probably the one you will want):

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

Upvotes: 4

Marc Gravell
Marc Gravell

Reputation: 1062550

There is no access to compiler-specific "builtin" instructions for things like ffs. You would have to use a regular code implementation using things like bitmasks and shift operations. However, that doesn't necessarily mean you need to iterate over all the bits: there are some scary-clever "regular" implementations for many of these methods, doing crazy "add some bizarre constant that isn't obvious" that are designed to cut out most of the branching and iteration, and which would be perfectly fine in C#. The main thing to keep in mind if you port one of these is knowing whether it is using "signed" or "unsigned" right-shifts; if it is using "signed" use int (etc); if it is "unsigned", use uint (etc).

Upvotes: 2

Related Questions