查找随机 BitshiftRight 组合

Question

我有问题。我试图找到右移操作的组合。一个例子。我有一个输入：

假设是 30。我现在找a和b什么的，这样a >> b = mynumber(30).

这是我的尝试：

private static Random rnd = new Random();
        private static int[] FindRightShift(int value)
        {
            int[] arr = new int[2];
            for (int i = 1; i < int.MaxValue; i++)
            {
                int b;
                if (int.TryParse((Math.Log(i / value) / Math.Log(2)).ToString(), out b))
                {
                    arr[0] = i;
                    arr[1] = b;
                    Console.WriteLine("{0} >> {1} = {2}", arr[0], arr[1], arr[0] >> arr[1]);
                    // return arr;
                }
            }
            return arr;
        }

这行得通，但需要很长时间，因为它会遍历所有组合。我如何修改我的函数，使其 return 一个随机组合（a 和 b）而不循环遍历所有？

Answer 1

我昨天向您发送了我的更新版本，据我测试，一切似乎都运行良好。欢迎大家指正。

主要概念是关于右移的一些数学运算： x / 2^y = number （其中 ^ 表示幂）

        int maxPower = (int)Math.Log(int.MaxValue, 2); // 30 -> max power to not exceed int.MaxValue

        maxPower = (int)Math.Log(Math.Pow(2, maxPower) / number, 2); // prevent "NOTE1" > int.MaxValue

        for (int y = 0; y < maxPower; y++) // outputs all possible numbers; can be replaced with Random.Next(1, maxPower+1)
        {
            int sub = (int)Math.Pow(2, y);
            int x = number * sub; // NOTE1

            Console.WriteLine("{0} >> {1} = {2}", x, y, x >> y);
        }

Answer 2

当前设置的主要问题是它不检查移位是否导致位移动 'off'。以字节为例，数字 12 将是： 00001100

意味着可以向左移动的最大字节数是 4。反之亦然，使用 y 的示例语法，也可以是最大 4（和 x 最大192) 对于 int 和其他有符号变量，有一个额外的行为，即当移动一个负值时，第一个（符号）位被不同地对待（见最后一段 here。将正数 1073741824 (1<<30) 向左移动一个位置，使其变为负数 (1<<31 == int.MinValue)，但将该数字向右移动，负号仍然存在，创建 -1073741824 .这意味着，最大移位的检查在正值和负值之间是不同的。

想到的方法，就是确定最大可以左移的位来确定max 'y'，做一个random(1,y)得到'y'使用，只需将数字向左移动 y 次即可得到 x。

private static void FindRightShift(int number)
{
    int maxshifts = 0, nr = number;
    Func<bool> check;
    if (number < 0) check = () => nr > (int.MinValue >> 1); else check = () => nr <  (1 << 30);
    while (check())
    {
        nr <<= 1;
        maxshifts++; //you could also opt to do a random break here
    }
    if (maxshifts ==0)
        throw new ArgumentException("Invalid number");
    int y = R.Next(1, maxshifts), x = number << y;
    //Debug.Assert((x >> y) == number);
    Console.WriteLine("{0} >> {1} = {2} (maxshifts: {3})", x, y, x >> y,  maxshifts);
}

另一种方法是继续尝试新的随机数，直到反转为真。重用您当前的代码：

    int x, y;
    do
    {
        y = R.Next(1, 30); // random valid power       
        x = number << y;
    } while (x >> y != number);
    Console.WriteLine("{0} >> {1} = {2}", x, y, x >> y);

查找随机 BitshiftRight 组合

Find Random BitshiftRight Combination

c#

reverse

bit-shift