CODEWITHSUNDEEP
c#bit-manipulation
yq8
yq8

Reputation: 145

Find two factors for right shift

Community,

Assume we have a random integer which is in the range Int32.MinValue - Int32.MaxValue. I'd like find two numbers which result in this integer when calculated together using the right shift operator.

An example :

If the input value is 123456 two possible output values could be 2022703104 and 14, because 2022703104 >> 14 == 123456

Here is my attempt:

 private static int[] DetermineShr(int input)
        {
            int[] arr = new int[2];

            if (input == 0)
            {
                arr[0] = 0;
                arr[1] = 0;
                return arr;
            }

            int a = (int)Math.Log(int.MaxValue / Math.Abs(input), 2);
            int b = (int)(input * Math.Pow(2, a));
            arr[0] = a;
            arr[1] = b;
            return arr;
        }

However for some negativ values it doesn't work, the output won't result in a correct calculation.

And for very small input values such as -2147483648 its throwing an exception :

enter image description here

How can I modify my function so it will produce a valid output for all input values between Int32.MinValue and Int32.MaxValue ?

Upvotes: 1

Views: 71

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186803

Well, let's compare

     123456     == 11110001001000000
  ‭   2022703104 == 1111000100100000000000000000000‬

can you see the pattern? If you're given shift (14 in your case) the answer is

 (123456 << shift) + any number in [0..2 ** (shift-1)] range

however, on large values left shift can result in integer overflow; if shift is small (less than 32) I suggest using long:

  private static long Factor(int source, int shift) {
    unchecked {
      // (uint): we want bits, not two complement
      long value = (uint) source;

      return value << shift;
    }
  }

Test: 

   int a = -1;
   long b = Factor(-1, 3);

   Console.WriteLine(a);
   Console.WriteLine(Convert.ToString(a, 2));
   Console.WriteLine(b);
   Console.WriteLine(Convert.ToString(b, 2))

will return 

   -1
   ‭11111111111111111111111111111111
   34359738360
   ‭11111111111111111111111111111111000‬

please, notice, that negative integers being two's complements

https://en.wikipedia.org/wiki/Two%27s_complement

are, in fact, quite large when treated as unsigned integers

Upvotes: 2

Related Questions