Tech Off Thread

13 posts

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

How do I read a variable's individual bits?

Back to Forum: Tech Off
  • User profile image
    Shining Arcanine

    I'm writing a prime number finder to learn C# and I have a number defined in a custom BigInteger data class. I would like to read its individual bits so if 345 (101011001) is stored I would be able to retrieve a boolean representation of, say the first bit on the left.

    I want to implement the trial factoring explained on this page:

    http://www.mersenne.org/math.htm

    Without the ability to read the top bit my program has no way of knowing whether or not to mutiple by 2 and that is a problem.

  • User profile image
    Shining Arcanine

    Coming from a PHP background, I kind of am used to having simple things like this done for me by preprogrammed functions so it was hard writing a num2bin function (especially without some of the building blocks that I was trying to find in .NET last night). For the first post I made I mentally converted 34 into binary in my head and after doing that it struck me. I could write a C# routine that would do exactly what I did mentally. If anyone is interested, here it is:

    Shining Arcanine wrote:

            private string num2bin(BigInteger number)
            {
                int i = 1;

                string bin = "";

                while (i < number)
                {
                    i *= 2;
                }

                i /= 2;

                while (number > 0)
                {
                    if (number - i > 0)
                    {
                        bin += "1";
                        number -= i;
                    }else
                    {
                        bin += "0";
                    }

                    i /= 2;
                }

                return bin;

            }


    I haven't tested it yet but it should work. If anyone needs the same thing, I hope this helps. Smiley

  • User profile image
    AndyC

    Shining Arcanine wrote:

    I haven't tested it yet but it should work. If anyone needs the same thing, I hope this helps. Smiley


    Manipulating strings is not the best way to handle this, it'll be incredibly slow, especially because you aren't using a StringBuilder.

    In any case C# already has bitwise operators (&,^,|,~,<<,>>) which can manipulate the numbers in the way you require. Since these are also implemented on the Biglnteger class you're using, it should be simple to do whet you want.

  • User profile image
    borosen

    Does not the "string ToString(int radix)" method of BigInteger do the trick?

  • User profile image
    Sven Groot

    Here's a function that can convert a number to any base (I've chosen to limit the highest base at 36 since you run out of letters of the alphabet if you go higher).

    private string IntToString(long number, int radix)
    {
    if( radix < 2 || radix > 36 )
    throw new ArgumentException("Invalid radix.", "radix");

    StringBuilder result = new StringBuilder();
    while( number > 0 )
    {
    long remainder = number % radix;
    if( remainder > 9 )
    result.Insert(0, (char)('A' + (remainder - 10)));
    else
    result.Insert(0, number % radix);
    number = number / radix;
    }

    return result.ToString();
    }



    You can make this faster if you only allow bin, oct and hex by using >> and & instead of / and %.

    If BigInteger indeed has a ToString(radix), it's likely to take care of it for you already.

  • User profile image
    Shining Arcanine

    borosen wrote:
    Does not the "string ToString(int radix)" method of BigInteger do the trick?


    Upon looking up the definition of radix (I'm in High School), it does. Thankyou.

    Thanks to Sven Groot too.

  • User profile image
    WillemM

    Ever tried low level bit comparison??

    int someVar = 11234;
    int resultVar = 11234 & 4;

    The resultvar will become 4 if the third bit (4 = 100) was set in the variable someVar.

  • User profile image
    Shining Arcanine

    WillemM wrote:
    Ever tried low level bit comparison??

    int someVar = 11234;
    int resultVar = 11234 & 4;

    The resultvar will become 4 if the third bit (4 = 100) was set in the variable someVar.


    Thanks for the tip. I tried rewriting my method and I discovered that I couldn't use the bitwise operators to find the correct value to seek to. In my code I have:

    BigInteger start = ((number | ~number) >> 1) + 1;

    It keeps becoming 0.

  • User profile image
    AndyC

    Shining Arcanine wrote:


    Thanks for the tip. I tried rewriting my method and I discovered that I couldn't use the bitwise operators to find the correct value to seek to. In my code I have:

    BigInteger start = ((number | ~number) >> 1) + 1;

    It keeps becoming 0.


    Not quite sure what you were aiming to do but (number | ~number) will always produce -1 (assuming two's complement arithmetic) and -1 >> 1 will always produce -1, hence the result you're getting.

  • User profile image
    Shining Arcanine

    I thought the OR operation did what this site specified:

    http://www.c-sharpcorner.com/Language/BitWiserOpsInCSCH001.asp

    Apparently the site is wrong. I was trying to take a number, change all of its bits to 1, remove one, and add a bit to one to get an exponent of two (e.g. 256, 8192, 16777216), that I could use to check whether or not a bit was there using WillemM's method. For each continuing bit I was going to subtract one to get it back into the form of all bits being 1, remove a bit and then add one to the number to the next exponent of two. I planned to continue this until the number became zero. That would allow me to implement trial factoring into my application and eliminate my inefficient use of strings:

    Shining Arcanine wrote:
           private static bool trialFactor(BigInteger number, BigInteger maxFactor, BackgroundWorker worker, DoWorkEventArgs e)
            {
                string text = number.ToString(2);
                int length = text.Length;

                for (BigInteger x = 3; x < maxFactor; x += 2)
                {

                    BigInteger num = 1;

                    for (int i = 0; length > i; i++)
                    {
                        if (worker.CancellationPending)
                        {
                            e.Cancel = true;
                        }
                        else
                        {
                            num *= num;

                            if (text[i] == '1')
                            {
                                num *= 2;
                            }

                            num %= x;
                        }
                    }

                    if (num == 1)
                    {
                        return true;
                    }
                }

                return false;
            }


    The current version of this that I have which uses bitwise operators like WillemM suggested is:

    Shining Arcanine wrote:
            private static bool trialFactor(BigInteger number, BigInteger maxFactor, BackgroundWorker worker, DoWorkEventArgs e)
            {

                BigInteger start = (number | ~number) >> 1;

                for (BigInteger x = 3; x < maxFactor; x += 2)
                {

                    BigInteger num = 1;

                    BigInteger temp = start;

                    while (temp > 0)
                    {
                        if (worker.CancellationPending)
                        {
                            e.Cancel = true;
                        }
                        else
                        {
                            num *= num;

                            if ((number & (temp + 1)) == temp)
                            {
                                num *= 2;
                            }

                            temp >>= temp  1;

                            num %= x;
                        }
                    }

                    if (num == 1)
                    {
                        return true;
                    }
                }

                return false;
            }


    The only problem is that I can't take the variable number and get another variable minus one bit with the remaining bits as 1.

    Edit: I was thinking, this kind of thing would be a heck of alot easier to do if I could write assembly to do it. I'll have to learn assembly to do it but at least it will run as fast as possible. Does anyone know if there is anyway to work with assembly in Microsoft Visual C# 2005 Express Edition?

  • User profile image
    AndyC

    Shining Arcanine wrote:
    I thought the OR operation did what this site specified:

    http://www.c-sharpcorner.com/Language/BitWiserOpsInCSCH001.asp

    Apparently the site is wrong.


    The site is correct, the OR is doing exactly what you want. It's the NOT that isn't. Why? Because your not thinking of the whole bit pattern.

    Assuming number is 10110, you're expecting ~number to be 01001 so that ORing them would produce 11111, right? However, you've got to remember that there are potentially an infinite number of leading zeroes procedeeing your number (in reality it's limited by the size of your datatype).

    If we imagine an 8-bit type, your sum now looks something like this:

    00010110  (number)
    11101001  (~number)

    11111111  (number | ~number)

    A little experimentation should convince you that end result will always have all bits set to 1 regardless of the datatype size, i.e. a result of -1.

    The easiest way I can think of to calculate the leftmost bit is to keep shifting the number left by one place until you get a value of zero. The count of times you need to shift it should tell you the highest power involved. 

  • User profile image
    borosen

    AndyC is right, and I don't want to spoil the lesson you are getting in bit-operations, but...

    Since you are using BigInteger, you could use the bitCount() method to find the position of the most significant bit.

  • User profile image
    Shining Arcanine

    AndyC wrote:
    Shining Arcanine wrote:I thought the OR operation did what this site specified:

    http://www.c-sharpcorner.com/Language/BitWiserOpsInCSCH001.asp

    Apparently the site is wrong.


    The site is correct, the OR is doing exactly what you want. It's the NOT that isn't. Why? Because your not thinking of the whole bit pattern.

    Assuming number is 10110, you're expecting ~number to be 01001 so that ORing them would produce 11111, right? However, you've got to remember that there are potentially an infinite number of leading zeroes procedeeing your number (in reality it's limited by the size of your datatype).

    If we imagine an 8-bit type, your sum now looks something like this:

    00010110  (number)
    11101001  (~number)

    11111111  (number | ~number)

    A little experimentation should convince you that end result will always have all bits set to 1 regardless of the datatype size, i.e. a result of -1.

    The easiest way I can think of to calculate the leftmost bit is to keep shifting the number left by one place until you get a value of zero. The count of times you need to shift it should tell you the highest power involved. 


    Thanks, I managed to get my method to function. I also realized that I had made a mistake when implementing trial factoring and I needed to use exponents instead of the actual mersenne numbers. This eliminated my need to use BigInteger in the method and I made me very happy until I realized that my method was outputting the wrong value for a certain exponent. Embarassed

    Thankfully the string version works correctly (with the corrections made to it) so I'm hoping the performance delta won't be too big.

    borosen wrote:
    AndyC is right, and I don't want to spoil the lesson you are getting in bit-operations, but...

    Since you are using BigInteger, you could use the bitCount() method to find the position of the most significant bit.


    Thanks for the tip. Unfortunately the numbers I'll be working with in this method (I found out that I was supposed to be using exponents instead of the actual mersenne numbers which are in the form 2^e - 1) are small enough to use the native data classes so I can't use bitCount(). I might need BigInteger if I decide to work with larger ones through.

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.