Andorid 算法之美 : 位运算

作者: as_pixar | 来源:发表于2020-03-07 20:53 被阅读0次

Andorid 算法之美 : 位运算
位运算之——按位与（&）操作——（快速取模算法）
递归、回溯、分治
位运算算法
leetcode算法总结之位运算
算法
大厂算法面试之leetcode精讲9.位运算
算法位运算总结
位运算小算法
算法很美--位运算

给定一个整数，请写一个函数判断该整数的奇偶性

该题目作为后续题目的铺垫，看上去还是没有任何难度的。主要考察了面试能否想到用二进制的位运算方法去解决。我们先回顾下 & | ~等运算符。

与运算符 &

两位同时为“1”，结果才为“1”，否则为“0”。

0&0=0; 0&1=0; 1&0=0; 1&1=1;

或运算符 |

只要有一位为1，其值为1，否则为0。
0|0=0； 0|1=1； 1|0=1； 1|1=1；

非运算符～

如果位为0，结果是1。如果位为1，结果是0

~0=1； ~1=0；

^ 异或运算符

两个操作数进行异或时，对于同一位上，如果数值相同则为 0，数值不同则为 1。

1 ^ 0 = 1,
1 ^ 1 = 0,
0 ^ 0 = 0;

3 ^ 5 = 6

值得注意的是 3 ^ 5 = 6,而 6 ^ 5 = 3

针对这个特性，我们可以将异或运算作为一个简单的数据加密的形式。比如，将一个mp4文件所有数值与一个种子数值进行异或得到加密后的数据，解密的时候再将数据与种子数值进行异或一次就可以了。

**所以说异或运算可以作为简单的加解密运算

>> 右移运算符

a >> b 将数值 a 的二进制数值从整体向右方向移动 b 位，正数符号位不变，高位空出来的位补数值 0。

5 >> 1 ===>  0000 0000 0000 0101 >> 1  = 0000 0000 0000 0010 = 2
7 >> 2 ===>  0000 0000 0000 0111 >> 2  = 0000 0000 0000 0001 = 1
9 >> 3 ===>  0000 0000 0000 1001 >> 3  = 0000 0000 0000 0001 = 1
11 >> 2 ===> 0000 0000 0000 1011 >> 2 = 0000 0000 0000 0010 = 2
大家发现什么规律没有？a >> b = a / ( 2 ^ b ) ,所以 5 >> 1= 5 / 2 = 2,11 >> 2 = 11 / 4 = 2。

<< 左移运算符

a << b 将数值 a 的二进制数值从整体向左方向移动 b 位，正数符号位不变，低位空出来的位补数值 0。

5 << 1 ===>  0000 0000 0000 0101 << 1  = 0000 0000 0000 1010 = 10
7 << 2 ===>  0000 0000 0000 0111 << 2  = 0000 0000 0001 1100 = 28
9 << 3 ===>  0000 0000 0000 1001 << 3  = 0000 0000 0100 1000 = 72
11 << 2 ===> 0000 0000 0000 1011 << 2 =  0000 0000 0010 1100 = 44
很明显就可以看出 a << b = a * (2 ^ b)

综合上面两个可以看到，如果某个数值右移 n 位，就相当于拿这个数值去除以 2 的 n 次幂。如果某个数值左移 n 位，就相当于这个数值乘以 2 ^ n。

场景一（或运算符的使用）

android:layout_gravity="bottom|right"

这里的 bottom 和 right 在位上肯定是错开的，这样做位运算，才能同时保存该控件 “居右”和“底部” 的属性。什么叫位上错开，且看下面代码

// 0x001 = 0000 0001
int right = 0x001;
// 0x002 = 0000 0010
int bottom = 0x002;
// 结果 = 0000 0011 = 3
System.out.println("right | bottom = " + (right | bottom));

通过上面的代码，或许你已经恍然大悟，其实位错开是为了或运算时，进行值的保留。 让两个或多个状态保存在一个属性中，目的是为了节省空间。

与运算符的使用

我们用或运算组装成一个值，要怎么使用它呢？安卓源码中怎么知道我们设置了 right 这个居右的状态呢？这个便需要使用 “与” 运算符来取值。具体操作如下代码：

int right = 0x001;
int bottom = 0x002;
int top = 0x008;
int state = right | bottom;
System.out.println("是否存在 right = " + ((state & right) == right));
System.out.println("是否存在 top = " + ((state & top) == top));

//运行结果 
是否存在 right = true
是否存在 top = false

非运算符的使用

如果我想剔除当前已经包含的一个值，需要怎么办？这时候就是“非”和“与”运算符联合使用的时候了，且看下面代码

int right = 0x001;
int bottom = 0x002;
int top = 0x008;
int state = right | bottom;
System.out.println("剔除 right 状态前 " + state);
state &= ~right;
System.out.println("剔除 right 状态后 " + state);
state &= ~top;
System.out.println("剔除不存在的 top 状态 " + state);

运行结果
剔除 right 状态前 3
剔除 right 状态后 2
剔除不存在的 top 状态 2

JVM 的基础数据字节长度是一致的

int：4 个字节。
short：2 个字节。
long：8 个字节。
byte：1 个字节。
float：4 个字节。
double：8 个字节。
char：2 个字节。
boolean：boolean属于布尔类型，在存储的时候不使用字节，仅仅使用 1 位来存储，范围仅仅为0和1，其字面量为true和false。

接下来我们看看原码反码补码。我们知道 int 型 4 个字节。每个字节 8 位。它的最高位是符号位。

最高位0表示正数。
最高位1表示负数

原码将一个数字转换成二进制就是这个数值的原码。

int a = 5; //原码  0000 0000 0000 0101
int b = -3;  //原码  1000 0000 0000 0011

反码

分两种情况：正数和负数

正数的反码就是原码。
负数的反码是在原码的基础上，符号位不变，其它位都取反。

5 的原码：0000 0000 0000 0101
5 的反码：0000 0000 0000 0101

-3 的原码：1000 0000 0000 0011
-3 的反码：1111 1111 1111 1100

补码

正数正数的补码就是原码。
负数负数的补码在反码的基础上加1

5 的补码：  0000 0000 0000 0101

-3 的原码：1000 0000 0000 0011
-3 的反码：1111 1111 1111 1100
-3 的补码: 1111 1111 1111 1101

计算机在进行数值运算的时候，是通过补码表示每个数值的。

5 - 3 = 5 + ( -3 )
相当于 0000 0000 0000 0101
 +    1111 1111 1111 1101
    =  0000 0000 0000 0010

整数可以分为正数，负数，0。也可以分为奇数和偶数。偶数的定义是：如果一个数是2的整数倍数，那么这个数便是偶数。如果不使用位运算的方法，我们完全可以使用下面的方式解决：

public boolean isOdd(int num){//odd 奇数
    return num % 2 != 0;
}

可是面试题不可能去简单就考察这么简单的解法，进而我们想到了二进制中如果一个数是偶数那么最后一个一定是 0 如果一个数是奇数那么最后一位一定是 1；而十进制 1 在 8 位二进制中表示为 0000 0001，我们只需将一个数个与1相与得到的结果如果是 1 则表示该数为奇数，否知为偶数。所以这道题的最佳解法如下：

public boolean isOdd(int num){
    return num & 1 != 0;
}

#include <stdio.h>
#include <math.h>

//函数声明
int isOdd(int num);

int  main()
{
    if( isOdd(0)>0)
    {
        printf("是奇数");
    }
    else
    {
        printf("是偶数");
    }
    return 0;
}

int  isOdd(int num)
{
    return (num & 1);
}

输出结果是偶数

同样给定一个整数，请写一个函数判断该整数是不是2的整数次幂

这道题仍旧考察面试者对于一个数的二进制的表示特点，一个整数如果是2的整数次幂，那么他用二进制表示完肯定有唯一一位为1其余各位都为 0，形如 0..0100...0。比如 8 是 2的3次幂，那么这个数表示为二进制位 0000 1000 。

除此之外我们还应该想到，一个二进制如果表示为 0..0100...0，那么它减去1得到的数二进制表示肯定是 0..0011..1 的形式。那么这个数减一,与上自己得到结果肯定为0。

所以该题最佳解法为：

public boolean IsLog2(int num){
   return (num & (num - 1)) == 0;
}

int IsLog2(int num){
       return (num & (num -1)) == 0;
}

//测试
int  main()
{
   printf("是否是2的整数次幂 ：%d\n",IsLog2(1));
   printf("是否是2的整数次幂 ：%d\n",IsLog2(2));
   printf("是否是2的整数次幂 ：%d\n",IsLog2(3));
    return 0;
}

结果
是否是2的整数次幂： 1 //是 true
是否是2的整数次幂： 1 //是 true
是否是2的整数次幂： 0 //不是 false

给定一个整数，请写一个函数判断该整数的二进制表示中1的个数

判断一个整数二进制表示中1的个数，假设这个整数用32位表示，可正可负可0，那么这个数中有多少个1，就需要考虑到符号位的问题了。

相信读者应该都能想到最近基本的解法即通过右移运算后与 1 相与得到的结果来计算结果，如果采用这种解法，那么这个题的陷阱就在于存在负数的情况，如果负数的话标志位应该算一个1。所以右移的时候一定要采用无符号右移才能得到正确的解法。

所以此题一种解法如下：

public int count1(int n) {
   int res = 0;
   while (n != 0) {
       res += n & 1;
       n >>>= 1;
   }
   return res;
}

#include <stdio.h>

int  bit(unsigned int n)
{
    int count=0;
    while (n != 0) {
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int main()
{
    printf("1在二进制中1的个数：%d\n",bit(1));
    printf("-1在二进制中1的个数：%d\n",bit(-1));
     printf("4在二进制中1的个数：%d\n",bit(4));
    return 0;
}

结果

1在二进制中1的个数：1
-1在二进制中1的个数：32
4在二进制中1的个数：1

在Android源码里面对于它的应用还是算是较多的，一般是用于存储多种变量，或者说是flag的存储和判断，在这里也就举几个例子。

MeasureSpec

兴许最早在Android源码里面接触位运算的话就是在自定义View部分的时候，当书里面提及MeasureSpec这个变量的时候采用如下描述：

MeasureSpec代表一个32位int值，高2位代表SpecMode，低30位代表SpecSize，SpecMode是指测量模式，而SpecSize是指在某种测量模式下的规格大小。

这里面就是典型的位运算的运用，不论是这个变量需要分别拆分获得 $\color{#34a853}{SpecMode}$ 和 $\color{#34a853}{SpecSize}$ ，还是其他的一些相关的操作，都需要位运算。

首先是 $\color{#34a853}{SpecMode}$ ，在描述之中是高2位的部分，那么在处理之中一定会运用到左移或者右移来完成需求。

在这个类里面，一开始就声明了两个基本变量以及不同测量模式的值，已经用到了位运算中的左移

private static final int MODE_SHIFT = 30;
// 声明位移量
private static final int MODE_MASK  = 0x3 << MODE_SHIFT;
// 后期截取SpecMode或SpecSize时使用的变量
// 3对应的二进制是11，左移30位后，int值的前2位就都是1，后30位为0

public static final int UNSPECIFIED = 0 << MODE_SHIFT;
public static final int EXACTLY     = 1 << MODE_SHIFT;
public static final int AT_MOST     = 2 << MODE_SHIFT;
// 三种测量模式对应的值

先看看是如何通过位运算来获取SpecMode和SpecSize：

@MeasureSpecMode
// 等价于@IntDef(value={...})。一种枚举类注释
public static int getMode(int measureSpec) {
    return (measureSpec & MODE_MASK);
    // 让低30位的值变为0，只保留高2位的值
}

public static int getSize(int measureSpec) {
    return (measureSpec & ~MODE_MASK);
    // 非运算直接让MASK值变成int值高2位为0，低30位为1
    // 进行与运算，直接将高2位的值变为0
}

这里就是典型的通过位运算来截取对应值，利用的是x & 1 = x, x & 0 = 0，其中x代表0与1两种值。这种方式让一个变量能够存储多个内容方式实现，甚至也可以使用这样的方式将合成的值作为特定的key来做匹配或者相似需求。

接下来是如何获得 $\color{#34a853}{MeasureSpec}$ 值：

public static int makeMeasureSpec(
    @IntRange(from = 0, to = (1 << MeasureSpec.MODE_SHIFT) - 1) int size,
    // 要求传入的size值在指定范围内
    @MeasureSpecMode int mode) {
            if (sUseBrokenMakeMeasureSpec) {// 是否用原来的方法对MeasureSpec进行构建
                return size + mode;
            } else {
                return (size & ~MODE_MASK) | (mode & MODE_MASK);
            }
        }

在API17及其以下的时候，是按照size + mode的方式进行构建，一个是只有int前2位有值，一个是只有int后30位有值，这么思考处理也情有可原。但假若两个值有溢出情况就会严重影响MeasureSpec的结果。故Google官方在API17之后就对该方法进行了修正，也是采用的位运算的形式：
(size & ~MODE_MASK) | (mode & MODE_MASK)
相当于就是分别获得了SpecSize和SpecMode后通过或运算获得结果。

Andorid 算法之美 : 位运算
给定一个整数，请写一个函数判断该整数的奇偶性该题目作为后续题目的铺垫，看上去还是没有任何难度的。主要考察了面试能...
位运算之——按位与（&）操作——（快速取模算法）
位运算之——按位与（&）操作——（快速取模算法） (2012-08-02 10:23:12) 分类:算法学习由于...
递归、回溯、分治
递归 (1)子集方式一：递归算法方式二：位运算算法（2）子集II 方法一：递归算法方法二：位运算（3）组...
位运算算法
位运算算法 -1.与: &或: |非: !异或 : ^ 相同为 0，不同为 1int 32 位 -> int ...
leetcode算法总结之位运算
First learn computer science and all the theory. Next dev...
算法
算法实战 | 图像处理, 宽度优先搜索, 位运算
大厂算法面试之leetcode精讲9.位运算
大厂算法面试之leetcode精讲9.位运算视频教程（高效学习）:点击学习[https://xiaochen10...
算法位运算总结
在位运算之前，对二进制需要掌握的基础知识正数的二进制，例如 5原码是 0000 0000 0000 0000 0...
位运算小算法
判断一个数是不是2的N次幂（能被2整除）swift篇按照二进制中只有一个1的时候才是2的N次幂，例如000000...
算法很美--位运算
2019/3/22更新题目1 : Exam07_TwoSingleNumbers时间限制:2000ms单点时限:...