位运算——强大得令人害怕Daioo 随笔-CSDN博客按位或运算

二进制位运算是直接使用二进制数进行运算，主要包含按位与，按位或，按位异或，取反，左移，右移

位运算基础

  • &
    • 按位与
    • 如果两个对应的二进制都为1，则该位的结果值为1，否则为0
  • |
    • 按位或
    • 两个相应的二进制位有一个为1，那么结果就为1
  • ^
    • 按位异或
    • 两个对应的二进制位如果不相等，则结果1，反之则为0
  • ~
    • 取反
    • 一元运算符，用来对一个二进制数按位取反，对于每一位，0变成1，1变成0
  • <<
    • 左移
    • 将一个数的各个二进制位全部左移N位，右边补0
  • >>
    • 右移
    • 将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数， 高位补0

位运算在算法中的使用技巧

【算法技巧】位运算装逼指南 - 掘金

判断奇数偶数：

一般的做法：通过对2取余数的结果来判断

  1. if(n % 2 == 0){
  2. // n是偶数
  3. }

但是通过二进制来看的话，只需要判断最后一个二进制位是0还是1就可以了。如果是0，那么就是偶数；如果是1，那么就是奇数。

  1. if(n & 1){
  2. // n是奇数
  3. }else{
  4. // n是偶数
  5. }

交换两个数的值

一般做法：引用一个额外的变量，作为中间值

  1. int tmp = x;
  2. x = y;
  3. y = tmp;

但是使用异或运算的话，我们不需要引用额外的变量

  1. x = x ^ y
  2. y = x ^ y
  3. x = x ^ y

找出没有重复的数据

给定一组整型数据，这些数据中，有且仅有一个数只出现了一次，其他的数都出现了两次，请你来找出这个数据。

首先要知道的是

  • 两个相同的数异或的结果为0，一个数和0异或的结果是他本身。
  • 异或运算是支持交换律和结合律的

那么我们不难想到，所有重复的数据都进行异或运算，得到0，最后唯一没有重复的数据和得到的0异或，得到我们的结果。所以只需要取数组中的第一个数temp，依次和后面的每一个数进行异或运算，最后temp的值就是没有重复数据的值

  1. int find(int[] arr){
  2.     int tmp = arr[0];
  3.     for(int i = 1;i < arr.length; i++){
  4.         tmp = tmp ^ arr[i];
  5.     }
  6.     return tmp;
  7. }