数据结构与算法--位运算

迷南。 2022-10-22 14:53 150阅读 0赞

#### 位运算 ####

*  记得大学编译原理刚开始面对的就是机器语言，而位运算就是讲数字用二进制标识后，对每一位上的0， 或者1 进行运算。二进制以及位运算都是计算机学科的基础，很多底层技术都离不开位运算，因此我们在实际开发过程中可能会遇到。由于我们人类熟悉的是十进制，因此接触到二进制的时候可能难以适应。
 *  除了二进制，我们还可以将数字表示成其他的进制，比如，表示分秒的六十进制等。针对不太熟悉的进制，可能会有一些奇奇怪怪的问题，比如下面这种：

/**在Excel中，用A表示第一列，B表示第二列......Z表示第26 列，AA表示27 列，AB表示28列......以此类推那么我们用一个函数，输入字母，输出列的编码是多少号*/
    /** * @author liaojiamin * @Date:Created in 16:30 2021/3/17 */
    public class NumberOfBit { 
        //字母转数字 A-Z ：1-26
        public static int letterToNumber(char letter) { 
            int num = (int)(letter - 'A' + 1) ;
            return num;
        }
    
        public static Long base26(String baseStr){ 
            if(baseStr == null){ 
                return -1L;
            }
            char[] charArray = baseStr.toCharArray();
            Long baseNumber = 26L;
            Long resultNum = 0L;
            double position = 0;
            for (int i = charArray.length -1; i >=0; i--) { 
                Double temp = Math.pow(baseNumber, position) * letterToNumber(charArray[i]);
                resultNum += temp.longValue();
                position++;
            }
            return resultNum;
        }
    
    
        public static void main(String[] args) { 
            System.out.println(base26("AA"));
            System.out.println(base26("AB"));
            System.out.println(base26("AZ"));
            System.out.println(base26("ZZ"));
            System.out.println(base26("AAA"));
        }
    }

*  如上其实就是讲A~Z理解成一个26进制，只要理解了二进制的计算规则，26进制也是同样的算法。
 *  二进制中位运算也就只有五种与， 或，异或，左移，右移。前三种用如下规则

与（&）：0&0 = 0， 1&0 = 0， 0&1 = 0， 1&1=1
    或（|）：0|0 = 0， 1|0 = 1. 0|1=1， 1|1 = 1
    异或（^）：0^0 = 0， 1^0=1， 0^1=1， 1^1 = 0

\-左移运算符m << n表示吧m左移n位，左移n位的时候，最左边的n位将被丢弃，同时最右边补充n个0，例如：

0000 1010 << 2 = 0010 1000
    1000 1010 << 3 = 0101 0000

*  右移运算符m >> 表示把m右移n位， 右移n为的时候，最右边的n为将被丢弃，当右移时候，处理最左边为的情形要稍微复杂一点
    
     *  如果是无符号数值，则用0 填补最左边的n为。
     *  如果是有符号数值，则用数字的符号位补充最左边的n位，也就是说如果数字是一个正数，右移后补充n个0 在左边，如果原数字是负数，则右移后最左边补充n个1.
     *  如下对两个8 为有符号数值做右移操作

0000 1010 >>2 == 0000 0010
    1000 1010 >>3 = 1111 0001

##### 具体案例分析 #####

*  题目：实现一个函数，输入一个整数，输出该整数二进制标识中1 的个数。例如把 9 标识成二进制后四位1001，有2位是1，因此如果输入9 ，函数输出2

###### 分析 ######

*  上题中考察二进制的知识，基本思路也就是利用那五种运算规则的组合来解答，可以先判断二进制数的最低位是不是1 ，将数值右移一位，接着判断最低位是否是1 ，继续如此直到数值为0 为止，
 *  现在需要确定怎么确定首位是1,：将整数与1 做 与操作，看结果是否是0 ，如果是0 则表示最低位是0 ，否则是1
 *  用9 为案例如下：

1001 & 1 = 1
    1001 >> 1 = 0100
    0100 & 1 = 0
    0100 >> 1 = 0010
    0010 & 1 = 0
    0010 >> 1 = 0001
    0001 & 1 = 1
    0001 >> 1 = 0000

*  以上我们可以得到如下代码：

/** * 正整数n 二进制表示中 1 的个数 * */
        public static int numberOf1(int n){ 
            int count = 0;
            while (n > 0){ 
                int andOne = n & 1;
                if(andOne == 1){ 
                    count ++;
                }
                n = n>>1;
            }
            return count;
        }

*  问题，以上代码都只考虑正数情况，正数右移是补充0 在最高位，所以能得出正常的解。我们用一个负数来举例，例如 -9 。
 *  首先必须要明确的是：\*\*\*负数在计算机中都是以补码来表示的。 负数的位运算也是在补码上进行的。\*\*\*这一点很重要
    
     *  我们用int类型为案例分析，int 32位有符号整型（-9） 的二进制标识：
     *  原码：1000 0000 0000 0000 0000 0000 0000 1001
     *  反码：1111 1111 1111 1111 1111 1111 1111 0110
     *  补码：1111 1111 1111 1111 1111 1111 1111 0111
 *  用以上算法对-9 进行右移的时候，在最左边补充的是1 ，因此不可能为0 ，因此会有死循环。

###### 正确解法 ######

*  上面的算法中我们思路是通过对求解的数进行右移来判断首位是否是1 ，既然不能通用，那么我们是否可能逐一判断数值的每一位二进制位上是否是1 。我们用flag表示 甄别是否是1 的数值 ，首先取flag = 1
 *  首先将数值与flag进行与操作，判断最低位是否是1 ，
 *  将flag 左移一位，继续与数值与操作，判断第二位是否为1
 *  继续如上操作，直到 flag的值为 0 ，（此时移动了32 位，超出int界限，所有位置都为0 ）
 *  我们可以得到如下算法实现：

/** * 通用二进制表示中 1 个数 * */
        public static int numberOf1_1(int n){ 
            int count = 0;
            int flag = 1;
            while (flag > 0){ 
                if((n & flag) > 0){ 
                    count ++;
                }
                flag = flag << 1;
            }
            return count;
        }

*  以上算法能统一解决带符号，和不带符号的数值的问题，并且对所有数值的计算都需要循环32 次，但是其实其中只有几次是有效的判断，比如1001 只有2 次，我们是否有更精简的方法。有几个1 就几次判断？

###### 最优解 ######

*  分析将一个数减1 ， 如果是不为0 的数，那么二进制表示中必然有1 ，假设这个数最右边一位是1，那么减1 的时候，最右边（低位）就会1 变0，而其他所有位不变。相当于最后一位取反。例子：

0000 1000 0010 0000 0110 0000 0000 0001 - 1 = 0000 1000 0010 0000 0110 0000 0000 0000

*  此时我们只能判断出第一位是不是1，此时我们还继续减1 ，那么假设第m位是1 ，这个时候，第m位 变为0 ，第m位以后的位都从0 变1 ，如下

0000 1000 0010 0000 0110 0000 0000 0000 - 1 = 0000 1000 0010 0000 0101 1111 1111 1111

*  这个时候1 变多了，如果继续减，显然不能达到我们目的，我们需要将后面多出来的1 都变成0 ，如下

0000 1000 0010 0000 0101 1111 1111 1111  --> 0000 1000 0010 0000 0100 0000 0000 0000

*  要达到如上目的，我们想到可以用与，或操作，两个都试试，如下：

//或操作
    0000 1000 0010 0000 0101 1111 1111 1111 | 0000 1000 0010 0000 0100 0000 0000 0000 = 0000 1000 0010 0000 0100 0000 0000 0000
    //与操作
    0000 1000 0010 0000 0101 1111 1111 1111 & 0000 1000 0010 0000 0110 0000 0000 0000 = 0000 1000 0010 0000 0100 0000 0000 0000

*  如上与，或，操作都能得到对应的值，但是与原值操作的对象，我们怎么得到呢，我们可以观察到，与操作中的操作对象的二进制值正好是原数据进行 -1 操作之前的二进制，那么问题就变的很简单了。
 *  我们将以上分析总结：
    
     *  将整数减去1，在和原整数做与操作，
     *  此时能将该整数最右边一个1 变成0 ，
     *  那么二进制表示中有多少个1 ，就可以进行多少次这种操作
     *  因此有如下算法

public static int numberOf1_2(int n){ 
            int count = 0;
            while (n != 0){ 
                n = n&(n-1);
                if(n != 0){ 
                    count ++;
                }
            }
            return count;
        }

##### 相关问题 #####

*  用一条语句判断一个整数是不是2 的整数次方
    
     *  一个整数是2 的整数次方，那么二进制表示中必然只有一个2，而其他所有位都是0
     *  同样依据解法三，将原数减1 后得到结果 ，将结果与原数进行与操作必然会变成0
 *  输入两个整数m，n。计算要改变m的二进制表中的多少位才能得到0,。例如10 的二进制 1010，与13的二进制1101
    
     *  此问题同样考察位操作，如上案例10， 和13，有三位二进制是不同的，我们如何通过二进制位操作甄别
     *  查看五种位操作，与，或，异或，左右移位，其中异或操作中两个二进制相同位数的值为0 ，不同的值为1
     *  利用这个特性， m ^ n 得到一个值x，我们只需要求解x 中1 的个数，就得到m与n中不同位数个数。

[上一篇：数据结构与算法–再谈递归与循环（斐波那契数列）][Link 1]  
[下一篇：数据结构与算法–代码完整性案例分析][Link 2]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/114886125
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/115199996