位运算技巧

1、判断奇偶数

一般做法:
if(( n % 2) == 1){ // n 是个奇数 }

如果把 n 以二进制的形式展示的话，其实我们只需要判断最后一个二进制位是 1 还是 0 就行了，如果是 1 的话，代表是奇数，如果是 0 则代表是偶数

if(n & 1 == 1){ // n 是个奇数。 }

2、交换两个数

一般做法，使用一个额外变量辅助交换：
int tmp = x; x = y; y = tmp;


使用位运算，不使用额外变量：
x = x ^ y // （1） y = x ^ y // （2） x = x ^ y // （3）

我们知道，两个相同的数异或之后结果会等于 0，即 n ^ n = 0。并且任何数与 0 异或等于它本身，即 n ^ 0 = n

3、找出没有重复的数

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

很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)了

两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身，所以我们把这一组整型全部异或一下，例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下
int find(int[] arr){ int tmp = arr[0]; for(int i = 1;i < arr.length; i++){ tmp = tmp ^ arr[i]; } return tmp; }

时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼

4、m的n次方

求解 m 的 n 次方，并且不能使用系统自带的 pow 函数，你会怎么做呢？这还不简单，连续让 n 个 m 相乘就行了
一般做法：
int pow(int n){ int tmp = 1; for(int i = 1; i <= n; i++) { tmp = tmp * m; } return tmp; }

举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:
m^1101 = m^0001 * m^0100 * m^1000。
我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果
int pow(int n){
    int sum = 1;
    int tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
   
    return sum;
}

时间复杂度近为 O(logn)，而且看起来很牛逼。

这里说一下，位运算很多情况下都是很二进制扯上关系的，所以我们要判断是否位运算，很多情况下都会把他们拆分成二进制，然后观察特性，或者就是利用与，或，异或的特性来观察，总之，我觉得多看一些例子，加上自己多动手，就比较容易上手了。所以呢，继续往下看，注意，先别看答案，先看看自己会不会做。

5、找出不大于N的最大的2的幂指数
传统的做法就是让 1 不断着乘以 2，代码如下：
int findN(int N){ int sum = 1; while(true){ if(sum * 2 > N){ return sum; } sum = sum * 2; } }

时间复杂度是 O(logn)，那如果改成位运算，该怎么做呢？我刚才说了，如果要弄成位运算的方式，很多时候我们把某个数拆成二进制，然后看看有哪些发现。这里我举个例子吧。

例如 N = 19，那么转换成二进制就是 00010011（这里为了方便，我采用8位的二进制来表示）。那么我们要找的数就是，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢？相应解法如下：
1、找到最左边的 1，然后把它右边的所有 0 变成 1
2、把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000。
3、把 得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000。
那么问题来了，第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢？我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1，
n |= n >> 1; n |= n >> 2; n |= n >> 4;

就是通过把 n 右移并且做或运算即可得到。我解释下吧，我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后，那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算，那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理，再次把 n 右移两位，那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算，那么就能得到第 k, k+1, k+2, k+3 都是 1，如此往复下去…

最终的代码如下
int findN(int n){ n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。 return (n + 1) >> 1; }

这种做法的时间复杂度近似 O(1)，重点是，高逼格。

我给出的这些例子中，并不是让你们学会了这些题就 Ok，而且让你们有一个意识：很多时候，位运算是个不错的选择，至少时间效率会快很多，而且高逼格，装逼必备。所以呢，以后可以多尝试去使用位运算哦，以后我会再给大家找些题来讲讲，遇到高逼格的，感觉很不错的，就会拿来供大家学习了

-------------------------------------------------------------------------------

https://blog.csdn.net/zengke1993/article/details/99830016

Java的位运算有以下几个：

  • 左移 ： <<
  • 右移 ： >>
  • 无符号右移 ： >>>
  • 与 ： &
  • 或 ： |
  • 非 ： ~
  • 异或： ^
有一个这样的例子： 水果 有各种特征， 有 大的，小的，甜的，酸的，便的，贵的。
那就可以这样定义这些属性：
public static final int  featureBig = 1; // 特征 大  ： 00000000 00000000 00000000 00000001   （int占四个字节，每个字节占8位）

public static final int  featureSmall = featureBig <<1 ; // 特征 小   00000010 （已省略前24位） 

public static final int featureSweet = featureBig <<2 ; //  特征 甜   00000100
   
public static final int featureSour = featureBig <<3 ; //  特征 酸   00001000

public static final int featureCheap = featureBig <<4 ; //  特征 便   00010000

public static final int featureExpensive = featureBig <<5 ; //  特征 贵  00100000


添加 |

那以西瓜为例， 首先初始化时
public static int watermelonFeatures = 0; // 西瓜的初始化特征

那西瓜的特征有 ： 大的， 甜的 ，便宜的 这几个特征， 那我们怎么添加呐？

watermelonFeatures |= featureBig | featureSweet | featureCheap; //特征：大/ 甜/便宜 00010101


判断 &

那现在要判断它是否有 “酸”的特征？ 怎么判断呐？ 用 &

watermelonFeatures & featureSour !=0 //false 00010101 & 00001000 -------------- 00000000 // 等0，所以false ，不包含 酸特征

再判断它是否有“甜”的特征？
watermelonFeatures & featureSour !=0 //false 00010101 & 00000100 -------------- 00000100 // 不等0，所以true ，包含 甜特征

移除 &~

那现在冬天了，西瓜过季了，涨价了。怎么移除这个便宜的特征呐? 用 ^
watermelonFeatures & ~featureCheap 00010101 & 11101111 (~00010000) -------------- 00000101 // 可见便宜特征又被移除


Android中使用位运算

android:layout_gravity="bottom|right"

在Intent.java中：
public static final int FILL_IN_ACTION = 1<<0;
 
  public static final int FILL_IN_DATA = 1<<1;
 
  public static final int FILL_IN_CATEGORIES = 1<<2;
 
  public static final int FILL_IN_COMPONENT = 1<<3;

mIntent.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK
                | Intent.FLAG_ACTIVITY_RESET_TASK_IF_NEEDED
                | Intent.FLAG_ACTIVITY_SINGLE_TOP
                );

public void setPressed(boolean pressed) {
     if (pressed) {
         mPrivateFlags |= PRESSED;     // 添加PRESSED状态
     } else {
         mPrivateFlags &= ~PRESSED;    // 取消PRESSED状态
     }
     refreshDrawableState();
     dispatchSetPressed(pressed);
 }


---------------------------------------------------
https://blog.csdn.net/qq_41995574/article/details/99227410

★★★由于位运算直接对内存数据进行操作，不需要转成十进制，直接在二进制上进行运算，因此处理速度非常快！！！

一、按位“与”运算符

按位“与”（Bitwise AND）,运算符号为：&
a&b 的操作结果：a、ba、ba、b中对应位同时为1，则对应结果位也为1，其余情况对应结果位为0

1. 用于整数的奇偶性判断

一个整数a，a&1这个表达式可以用来判断a的奇偶性。二进制的末尾位为0表示偶数，末尾位为1表示奇数。使用a%2来判断奇偶性和a&1是一样的作用，但是a&1要快好多。

2. 判断a是否是2的正整数幂

如果一个数a是2的正整数幂，那么a的二进制形式必定为100000....(最高位为1，之后有0个或多个0，注意：2^0 =1，而a−1的二进制形式必定是111111...，但当a=1时， a−1=0)。若a是2的正整数幂，则必有a&(a−1)结果为0

3. 统计二进制数a中1的个数

朴素的统计方法是： 先判断n的奇偶性，为奇数时计数器增加1，然后将a右移一位，重复上面的步骤，知道移位完毕
公式法： a&(a−1) 的作用是消掉二进制数a中最低位的1。将a&(a−1) 的结果重新赋值给a，继续进行此操作，直到赋值结果为0时终止，重复的次数即为a中1的个数

二、按位“异或”运算符


按位“异或”，运算符号为：⋀
a⋀b 的操作结果：a、b中对应位相异时(即：一个为0，一个为1)，则对应结果位为1，其余情况对应结果位为0

知识点：
  1. 任何数和0异或为任何数：0 ^ n => n
  2. 相同的数异或为0：n ^ n => 0
  3. 满足交换律a ^ b ^ c <=> a ^ c ^ b

1. 不使用临时变量，交换a和b的值

a = 7 b = 5 a = a^b b = b^a a = a^b

2. 除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

相同的数异或为0：n ^ n => 0，且，满足交换律a ^ b ^ c <=> a ^ c ^ b

只要让数组中的元素依次相“异或”，出现两次的元素最终异或为0，仅剩下唯一只出现过一次的元素








参考：
https://blog.csdn.net/m0_37907797/article/details/103120886
https://blog.csdn.net/zengke1993/article/details/99830016
https://blog.csdn.net/qq_41995574/article/details/99227410
https://www.cnblogs.com/bytebee/p/8194677.html
https://blog.csdn.net/weixin_42110638/article/details/86594605




时间：