Простое понимание побитовых операций из трех вопросов LeetCode

Сколько из этих вопросов вы ответили?

В процессе подготовки к собеседованию чистка вопросов по алгоритму — обязательный курс, и я, конечно же, не исключение. Однажды я наткнулся на волшебную тему:

# 136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

Не могу не нахмуриться, в душе думаю, это не просто, записываем следующий код:

  /**
   * HashMap
   *
   * @param nums 数组
   * @return 结果
   */
  public int solution(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
      if (map.containsKey(num)) {
        map.remove(num);
      } else {
        map.put(num, 1);
      }
    }
    return map.entrySet().iterator().next().getKey();
  }

Потом увидел другую тему:

# 137. 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,3,2]
输出: 3

示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99

Я снова не мог не нахмуриться, мысленно думая, что это, кажется, та же рутина, поэтому я написал следующий код:

  /**
   * 使用Map，存储key以及出现次数
   *
   * @param nums 数组
   * @return 出现一次的数字
   */
  public int singleNumber(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
      if (map.containsKey(num)) {
        map.put(num, map.get(num) + 1);
      } else {
        map.put(num, 1);
      }
    }
    for (Integer key : map.keySet()) {
      if (map.get(key) == 1) {
        return key;
      }
    }
    return 0;
  }

Тогда возникает последний вопрос:

# 260. 只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]

注意：
1. 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

Я снова не мог не нахмуриться и сказал, эм... Затем я написал следующий код:

  /**
   * 使用Map，存储key以及出现次数
   *
   * @param nums 数组
   * @return 出现一次的数字的数组
   */
  public int[] singleNumber(int[] nums) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
      if (map.containsKey(num)) {
        map.put(num, map.get(num) + 1);
      } else {
        map.put(num, 1);
      }
    }
    int i = 0;
    for (Integer key : map.keySet()) {
      if (map.get(key) == 1) {
        result[i] = key;
        i++;
      }
    }
    return result;
  }

Я сделал три вопроса почти с одной и той же идеей, и мне пришлось похвалить себя:

После выполнения этих трех вопросов и отправки ответов время выполнения и потребление памяти превысили только 10% решателей задач. Я не мог не нахмуриться (наконец-то я понял, почему моя татуировка на лбу такая глубокая), и обнаружил, что все не так просто...

После этого я нашел другое решение, а именно:

  /**
   * #136 根据题目描述，由于加上了时间复杂度必须是 O(n) ，并且空间复杂度为 O(1) 的条件，因此不能用排序方法，也不能使用 map 数据结构。答案是使用 位操作Bit Operation 来解此题。
   * 将所有元素做异或运算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的结果就是那个只出现一次的数字，时间复杂度为O(n)。
   * 根据异或的性质 任何一个数字异或它自己都等于 0
   *
   * @param nums 数组
   * @return 结果
   */
  private int solution(int[] nums) {
    int res = 0;
    for (int num : nums) {
      res ^= num;
    }
    return res;
  }

  /**
   * #137 嗯……这个我们下面再做详解
   * 这里使用了异或、与、取反这些运算
   *
   * @param nums 数组
   * @return 出现一次的数字
   */
  public int singleNumber2(int[] nums) {
    int a = 0, b = 0;
    int mask;
    for (int num : nums) {
      b ^= a & num;
      a ^= num;
      mask = ~(a & b);
      a &= mask;
      b &= mask;
    }
    return a;
  }

  /**
   * #260 在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。
   * 然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。
   * 根据异或的性质 任何一个数字异或它自己都等于 0 ，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。
   * 再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。
   * 1. 将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个
   * 2. 将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。
   * 这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。
   * 
   * 使用位运算
   *
   * @param nums 数组
   * @return 只出现一次数字的数组
   */
  public int[] singleNumber2(int[] nums) {
    int diff = 0;
    for (int num : nums) {
      diff ^= num;
    }
    // 得到最低的有效位，即两个数不同的那一位
    diff &= -diff;
    int[] result = new int[2];
    for (int num : nums) {
      if ((num & diff) == 0) {
        result[0] ^= num;
      } else {
        result[1] ^= num;
      }
    }
    return result;
  }

После прочтения приведенного выше решения у меня в голове только вопросительный знак, что это значит? !

Давайте кратко разберемся с битовой операцией и проанализируем эти три темы.

Краткое введение в битовые операции

1. Операция исключающее ИЛИ (^)

Взаимосвязь логики XOR такова: когда AB разные, выход P=1, когда AB одинаковый, выход P=0. «⊕» — это символ математической операции XOR, а логика XOR также является комбинацией логики AND-OR, и ее логическое выражение:П=А⊕В. В компьютерных языках символом XOR является «^».

Таблица истинности операции XOR A ⊕ B выглядит следующим образом:

A	B	⊕
F	F	F
F	T	T
T	F	T
T	T	F

Итак, мы начинаем с#136В решении понимается, что через операцию XOR результат двух одинаковых элементов равен 0, алюбой номери0операция XOR, результат сам по себе.

2. И операция (&)

Операция «И» является основным методом логической операции в компьютере, и символ выражается как «&». Правила работы: 0&0=0; 0&1=0; 1&0=0; 1&1=1; то есть, если два бита одновременно равны "1", результат равен "1", иначе - 0. Кроме того, отрицательные числа участвуют в побитовой операции И в форме дополнения.

Таблица истинности для операции AND A и B выглядит следующим образом:

A	B	&
F	F	F
F	T	F
T	F	F
T	T	T

Специальное использование «И»:

чистый. Если вы хотите очистить ячейку, даже если все ее двоичные биты равны 0, пока она объединяется по И со значением, все биты которого равны нулю, результат равен нулю.
взять указанную цифру числа

Метод: Найдите число, которое соответствует биту, который должен быть взят X. Соответствующий бит числа равен 1, а остальные биты равны 0. Операция «И» между этим числом и X может получить указанный бит в X. Пример: Установите X=10101110, возьмите младшие 4 бита X, используйтеX & 0000 1111 = 0000 1110Его можно получить; его также можно использовать для получения 2, 4 и 6 бит X.

3. Или операция (|)

Два объекта, участвующих в операции, «обрабатываются» в соответствии с двоичным битом. Правила операции: 0|0=0; 0|1=1; 1|0=1; 1|1=1; то есть: пока один из двух объектов, участвующих в операции, равен 1, его значение равно 1. Кроме того, отрицательные числа участвуют в побитовой операции ИЛИ в форме дополнения.

Таблица истинности для операции ИЛИ A | B выглядит следующим образом:

A	B	\|
F	F	F
F	T	T
T	F	T
T	T	T

ИЛИ операция" специальная функция:

Он часто используется для установки определенных позиций в данных.

Метод: Найдите число, соответствующее биту, который должен быть установлен в 1 в X, соответствующий бит числа равен 1, а остальные биты равны нулю. Это число находится в фазе с X или может устанавливать некоторые позиции в X.

Пример: Установите младшие 4 бита X=10100000 в 1, используйтеX | 0000 1111 = 1010 1111может быть получен.

4. Отрицательная операция (~)

Часть данных, участвующих в операции, «инвертируется» в соответствии с двоичным битом. Правила работы: ~1=0; ~0=1, то есть побитовая инверсия двоичного числа, то есть 0 становится 1, а 1 становится 0.

Чтобы сделать младший значащий бит числа равным нулю, его можно выразить так:a&~1. Значение ~1 равно 11111111111111110, а затем нажмите операцию «И», младший бит должен быть равен 0. Потому что оператор "~" имеет более высокий приоритет, чем арифметические операторы, операторы отношения, логические операторы и другие операторы.

Итак, битовые операции, используемые в трех темах, были введены, так что давайте вставим их сюда.#137подробное решение.

public int singleNumber2(int[] nums) {
    // 这里我们改一下变量名
    // 用 one 记录到当前处理的元素为止，二进制1出现“1次”（mod 3 之后的 1）的有哪些二进制位；
    // 用 two 记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的有哪些二进制位。
    int one = 0, two = 0;
    int mask;
    for (int num : nums) {
      // 由于 two 要考虑，one 的已有状态，和当前是否继续出现。所以要先算
      two ^= one & num;
      // one 就是一个0,1的二值位，在两个状态间转换
      one ^= num;
      // 当 one 和 two 中的某一位同时为1时表示该二进制位上1出现了3次，此时需要清零。
      mask = ~(one & two);
      // 清零操作
      one &= mask;
      two &= mask;
    }
    // 即用 二进制 模拟 三进制 运算。最终 one 记录的是最终结果。
    return one;
  }

Сначала рассмотрим относительно простую задачу: во входном массиве только 0 и 1. Нам нужно подсчитать количество вхождений 1. Когда встречается 1, количество раз увеличивается на 1, а когда встречается 0, остается неизменным возвращается к 0. Мы можем выполнить эту счетную работу с m битами, т.е.x_m, x_м−1, …,x₁, просто убедитесь, что 2^m> k достаточно, следующий вопрос, который нам нужно рассмотреть, — какую операцию выполнять, чтобы выполнить вышеуказанные условия каждый раз, когда элемент проверяется. Перед началом подсчета каждый бит счета инициализируется битом 0, а затем повторяется.nums, пока не встретится первая 1, после чего x₁станет 1 и продолжит перемещение до тех пор, пока не встретится вторая 1, и в этот момент x₁=0, x₂=1, пока здесь вы не сможете увидеть закон. Каждый раз, когда встречается 1, дляx_m, x_м−1, …,x₁, вам нужно изменить его значение только тогда, когда все предыдущие биты равны 1. Если он изначально был 1, он становится 0. Если он был 0, он становится 1. Если он встречает 0, он остается неизменным. Как только вы поймете эту логику, писать выражения будет несложно. Здесь m = 3 приведено в качестве примераjavaКод:

for(int num: nums) {
    x3 ^= x2 & x1 & num;
    x2 ^= x1 & num;
    x1 ^= num;
    // other operations
}

Но здесь мы не решили проблему, заключающуюся в том, что когда число 1 достигает k, значение счетчика должно снова вернуться к 0, то есть все биты счетчика становятся равными 0. Решение тоже весьма умное.

Предположим, у нас есть переменная флага, которая равна 0 только тогда, когда значение счетчика достигает k, и 1 в остальных случаях, а затем выполняет операцию И над каждым битом счетчика и переменной флага каждый раз, когда проверяется элемент. переменная флага равна 0, то есть, когда значение счетчика равно k, все биты станут равными 0, в противном случае все биты останутся неизменными, тогда наша цель достигнута.

Ну и последний вопрос, как вычислить значение переменной флага. Преобразование k в двоичное, только когда значение счетчика достигнет k, все биты счетчика будут такими же, как двоичные биты k, поэтому необходимо выполнить только двоичные биты k.с операцией, если бит равен 0, то жеотрицатьЗначение после этого объединяется по И.

Взяв в качестве примера k=3, m=2, краткийjavaкод показывает, как показано ниже:

// where yj = xj if kj = 1, 
// and yj = ~xj if kj = 0, 
// k1, k2是 k 的二进制表示(j = 1 to 2). 
mask = ~(y1 & y2); 
x2 &= mask;
x1 &= mask;

Соединение этих двух частей вместе представляет собой полный алгоритм решения этой проблемы.

5. Оператор сдвига влево (

Сдвигает все двоичные биты операнда влево на несколько битов (левые двоичные биты отбрасываются, а правая часть заполняется 0).

Пример: a = a

Если старшие биты, отбрасываемые при сдвиге влево, не содержат 1, каждый сдвиг влево эквивалентен умножению числа на 2.

Пример кода, целое число в этом коде является 32-битным целым числом, поэтому, если это отрицательное число, двоичное представление имеет длину 32:

    /**
     * << 表示左移，如果该数为正，则低位补0，若为负数，则低位补1。如：5<<2的意思为5的二进制位往左挪两位，右边补0，5的二进制位是0000 0101 ， 就是把有效值101往左挪两位就是0001 0100
     */
    @Test
    public void leftShiftTest() {
        int number1 = 5;
        System.out.println("左移前的十进制数为：" + number1);
        System.out.println("左移前的二进制数为：" + Integer.toBinaryString(number1));
        int number2 = number1 << 2;
        System.out.println("左移后的十进制数为：" + number2);
        System.out.println("左移后的二进制数为：" + Integer.toBinaryString(number2));
        System.out.println();
        int number3 = -5;
        System.out.println("左移前的十进制数为：" + number3);
        System.out.println("左移前的二进制数为：" + Integer.toBinaryString(number3));
        int number4 = number3 << 2;
        System.out.println("左移后的十进制数为：" + number4);
        System.out.println("左移后的二进制数为：" + Integer.toBinaryString(number4));
    }

Результат выглядит следующим образом:

左移前的十进制数为：5
左移前的二进制数为：101
左移后的十进制数为：20
左移后的二进制数为：10100

左移前的十进制数为：-5
左移前的二进制数为：11111111111111111111111111111011
左移后的十进制数为：-20
左移后的二进制数为：11111111111111111111111111101100

6. Оператор сдвига вправо (>>)

>>Представляет сдвиг вправо, что означает, что все двоичные биты числа сдвигаются вправо на несколько битов, положительные числа остаются с 0, отрицательные числа остаются с 1, а правая часть отбрасывается. Каждый сдвиг операнда вправо эквивалентен делению числа на 2.

>>>Представляет сдвиг вправо без знака, также называемый логическим сдвигом вправо, то есть, если число положительное, старший бит заполняется 0, а если число отрицательное, старший бит также заполняется 0 после правильный сдвиг.

Например:a = a >> 2Сдвиньте двоичные биты a вправо на 2 бита и добавьте 0 или 1 влево в зависимости от того, является ли сдвинутое число положительным или отрицательным.

    @Test
    public void rightShift() {
        int number1 = 10;
        System.out.println("右移前的十进制数为：" + number1);
        System.out.println("右移前的二进制数为：" + Integer.toBinaryString(number1));
        int number2 = number1 >> 2;
        System.out.println("右移后的十进制数为：" + number2);
        System.out.println("右移后的二进制数为：" + Integer.toBinaryString(number2));
        System.out.println();
        int number3 = -10;
        System.out.println("右移前的十进制数为：" + number3);
        System.out.println("右移前的二进制数为：" + Integer.toBinaryString(number3));
        int number4 = number3 >> 2;
        System.out.println("右移后的十进制数为：" + number4);
        System.out.println("右移后的二进制数为：" + Integer.toBinaryString(number4));

        System.out.println("***********************逻辑右移**********************");

        int a = 15;
        System.out.println("逻辑右移前的十进制数为：" + a);
        System.out.println("逻辑右移前的二进制数为：" + Integer.toBinaryString(a));
        int b = a >>> 2;
        System.out.println("逻辑右移后的十进制数为：" + b);
        System.out.println("逻辑右移后的二进制数为：" + Integer.toBinaryString(b));
        System.out.println();
        int c = -15;
        System.out.println("逻辑右移前的十进制数为：" + c);
        System.out.println("逻辑右移前的二进制数为：" + Integer.toBinaryString(c));
        int d = c >>> 2;
        System.out.println("逻辑右移后的十进制数为：" + d);
        System.out.println("逻辑右移后的二进制数为：" + Integer.toBinaryString(d));
    }

Результат выглядит следующим образом:

右移前的十进制数为：10
右移前的二进制数为：1010
右移后的十进制数为：2
右移后的二进制数为：10

右移前的十进制数为：-10
右移前的二进制数为：11111111111111111111111111110110
右移后的十进制数为：-3
右移后的二进制数为：11111111111111111111111111111101
***********************逻辑右移**********************
逻辑右移前的十进制数为：15
逻辑右移前的二进制数为：1111
逻辑右移后的十进制数为：3
逻辑右移后的二进制数为：11

逻辑右移前的十进制数为：-15
逻辑右移前的二进制数为：11111111111111111111111111110001
逻辑右移后的十进制数为：1073741820
逻辑右移后的二进制数为：111111111111111111111111111100

Суммировать

Выше приведены некоторые из наших общих битовых операций, включая сдвиг влево, сдвиг вправо и другие операции вHashMapИсходный код .

Как видно из некоторых приведенных выше примеров, битовые операции обычно используются для сокращения сложных операций, включая перестановку и подсчет.Конечно, они также могут использоваться для замены основных операций, таких как умножение на 2 и деление на 2, оценка простых чисел. , четные числа и кратные.Однако я думаю, что значение заключается в первом, то есть в использовании счетчиков для уменьшения сложности проблемы проектирования до перестановки или подсчета.

Последний пункт, в трех вопросах алгоритма,#136,#260Это нормально понимать.#137 Single Number IIМожет потребоваться немного усилий, чтобы решить проблему, по крайней мере, я еще не до конца ее понял, но я не могу так просто сдаться, правильно, продолжайте копать!

Вышеизложенное является моим личным кратким резюме, если есть какие-то упущения или ошибки, прошу указать и исправить.

Ссылаться на:

Сводка проблем с одним номером Leetcode
Графический LeetCode -- # 136 Числа, которые появляются только один раз
Буквенный код для решения проблем - # 137 Single Number II
#137 SingleNumber II discuss