1

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?

Community
  • 1
  • 1
Heisenbug
  • 38,762
  • 28
  • 132
  • 190
  • possible duplicate of [\_BitScanForward in C#?](http://stackoverflow.com/questions/9090061/bitscanforward-in-c) – Rawling Jan 21 '13 at 10:25
  • Possible duplicate of [Number of unset bit left of most significant set bit?](http://stackoverflow.com/questions/4097257/number-of-unset-bit-left-of-most-significant-set-bit) – Jim Balter Dec 27 '16 at 22:19

4 Answers4

4

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));
        }
    }
}
Matthew Watson
  • 104,400
  • 10
  • 158
  • 276
  • 1
    Interesting. In the `uint` case, the `LeastSigBitSet` method, you take bitwise "and" of two `long` (`Int64`, signed 64-bit integers), and then narrow to `uint` (`UInt32`). But you can also say `return value & 0u - value;` and then everything will be 32-bit. However, it requires the overflow checking context to be `unchecked` (which it will normally be). – Jeppe Stig Nielsen Jan 21 '13 at 14:54
  • Good point. We can also change it to "return (uint)((int)value & -(int)value);", which also avoids conversion to 64 bits. I prefer your shorter version though - I'll update my answer. – Matthew Watson Jan 21 '13 at 16:31
  • I might be missing something here - but what's wrong with `(value&(~value+1))` ? for `111111110000` it will show `16` – Royi Namir May 17 '15 at 08:38
  • @RoyiNamir This is for `LeastSigBitSet()` I assume. Well, `(value&(~value+1))` uses an AND, a NOT and an ADD. My `(value & 0u-value)` uses just an AND and a SUBTRACT. Therefore it is more efficient. – Matthew Watson May 18 '15 at 09:49
  • @MatthewWatson Yes. less operation I agree. but regarding to your code - why didnt you just do `value & -value` ? but `(value & 0u-value)` – Royi Namir May 18 '15 at 20:50
  • @RoyiNamir Because `value & -value` won't compile: `Cannot implicitly convert type 'long' to 'uint'` – Matthew Watson May 19 '15 at 08:09
  • -1 What is wanted is a bit number, but you are returning the bit mask. Look at the OP's link, http://stackoverflow.com/questions/9093323/efficient-bitwise-operations-for-counting-bits-or-find-the-rightleft-most-ones, which counts bits, and again at your link ... for the number of the highest bit set, use http://aggregate.org/MAGIC/#Log2 ... for the number of the lowest bit set, take log2 of your LeastSigBitSet. – Jim Balter Dec 27 '16 at 22:11
  • P.S. See also http://stackoverflow.com/questions/4097257/number-of-unset-bit-left-of-most-significant-set-bit – Jim Balter Dec 27 '16 at 22:18
  • @JimBalter I was answering the actual question, rather than something which the OP says is "like" the thing he wants. And the question is specifically asking for an `efficient bitwise operation to find left|right most bit set` - not an `efficient bitwise operation to find the *index* of the left|right most bit set`. – Matthew Watson Dec 29 '16 at 16:34
  • The "actual question" is the one that the OP wants answered, and that is precisely about finding the index, as the OP's link makes clear. Others understood this, which is why, for instance, there's a dup link to _BitScanForward, and the accepted answer mentions ffs. End of discussion. – Jim Balter Dec 30 '16 at 04:16
2

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).

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
  • thanks..do you personally know(or have a reference to) any "scary-clever "regular" implementations for many of these methods" to suggest me? – Heisenbug Jan 21 '13 at 10:30
  • +1 Sensibile answer and it features legitimate use of `ffs` and it not meaning the usual... :-D – Tom Chantler Jan 21 '13 at 10:31
2

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

M.Toy
  • 103
  • 7
0

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);
Nissa
  • 4,636
  • 8
  • 29
  • 37
Chris Roberts
  • 1
  • 1