时间戳

首页 > 解决方案 > 位循环移位

java - 位循环移位

问题描述

我目前正在学习按位运算，我的任务是对 4 位整数进行左旋转。

我的 4 位左旋转代码是

private static int BITS_IN_INTEGER = 4;

private static int leftRotate(int x, int n) {
  return (x << n) | (x >> (BITS_IN_INTEGER - n));
}

我想进行 4 位循环移位以在旋转后保持为 4 位，但似乎无法理解它是如何工作的。

示例：左旋转 1 位后的 10 (1010) 会给我 5 (0101) 但它给我的值 21 比我的 4 位多。

任何让我理解这个问题的帮助将不胜感激！

标签： javabitwise-operatorsbit

解决方案

如果我理解正确，你想

  • 模拟具有BITS_IN_INTEGER多位而不是 32 位的整数。
  • 对这样一个模拟整数进行旋转

目前您可以进行旋转，但不属于模拟 int 的实际 int 的高位可能会以 0 以外的值结束。例如：

intput x
0000 0000  0000 0000  0000 0000  0000 1100
                                     |____|___, emulated int
result of rotating left by n=2       |    |
0000 0000  0000 0000  0000 0000  0011 0011

正如我们所看到的，我们所要做的就是将模拟 int 上方的位（即 32 -BITS_IN_INTEGER高位）设置为零。为此，我们使用逻辑“与” ( &)。我们需要一个掩码，它包含0我们想要设置为零的位（任何东西& 0总是 0）和1我们想要保留的位（任何东西& 1总是任何东西）。

  0...0  0011 0011  ←  the result from before
& 0...0  0000 1111  ←  a mask
——————————————————
  0...0  0000 0011  ←  the masked result where unused bits are 0

要生成0...01...1具有BITS_IN_INTEGER许多1s 形式的掩码，我们可以使用(1 << BITS_IN_INTEGER) - 1. - 1转换10000为01111. _

static int BITS_IN_INTEGER = 4;
static int INTEGER_MASK = (1 << BITS_IN_INTEGER) - 1;

static int leftRotate(int x, int n) {
  return INTEGER_MASK & ((x << n) | (x >>> (BITS_IN_INTEGER - n)));
}

推荐阅读