【二进制和位运算】一、认识二进制和位运算

阳光穿透心脏的1/2处 2023-10-09 14:23 109阅读 0赞

#### 文章目录 ####

*  一、什么是二进制，它和十进制的区别是什么？
 *  二、二进制和十进制如何相互转换？
 *   *  三、算法基础之位运算
     *  四、经典面试题
     *   *  1、处死偶数囚犯面试题
         *  2、老鼠试药问题：

## 一、什么是二进制，它和十进制的区别是什么？ ##

*  进位条件不一致，十进制讲究逢十进一因此每一位只有0-9这十个数。
 *  二进制则是逢二进一，所以每一位只有0和1两种选择。
 *  但不论二进制还是十进制，其实只是对同一个数的不同表示方式罢了，本质都是相同的。

*  计算机中为什么使用二进制进行数据的存储。
 *  1、技术上很容易实现

用双稳态电路很容易表示二进制数0和1。

2、高可靠性

二进制系统中只使用两位数0和1，所以在传输和处理中不容易出错，从而保证了计算机的高可靠性。

3、简单的操作规则

与十进制数相比，二进制数的运算规则要简单得多，这不仅简化了运算单元的结构，而且有助于提高运算速度。

4、逻辑量

二进制数0和1完全对应于逻辑量“真”和“假”，因此使用二进制数来表示二进制逻辑是很自然的

5、二进制数和十进制数之间的转换非常容易

当人们使用计算机时，他们仍然可以使用他们惯用的十进制数字。计算机会自动将它们转换成二进制数进行存储和处理，并在输出处理结果时自动将二进制数转换成十进制数，给工作带来极大的方便。

## 二、二进制和十进制如何相互转换？ ##

二进制转十进制：
        一个二进制数1101从右至左分别为2的0次方、2的1次方、
       2的2次方……为1表示有这个值，然后将其有值的数相加
       即可得到其所对应的十进制的数如上例，其所对应的十进制
       为：1 + 4 + 8 = 13

System.out.println("十进制的数为："+Integer.parseInt("1101", 2));

十进制转二进制：
        一个十进制数23，将其除以2得到余数，然后将商再除以2，再得到余数
      用其商再除以2……直到商为0为止，将所得到的余数由下往上写即可得到其所
        对应的二进制的数。
            23/2 = 11   余 1 
            11/2 = 5   余 1 
            5/2 = 2   余 1 
            2/2 = 1   余 0 
            1/2 = 0   余1
         * 那么其所对应的二进制就为：10111

System.out.println("二进制的数为："+Integer.toBinaryString(23));

### 三、算法基础之位运算 ###

*  在计算机中，都是以2进制的方式对数据进行存储，而一个int型的自然数对其进行>>和>>>效果一样，
 *  因为其最高位都为0，而对于int型的负数而言，其最高位为1，所以>>后的最高位将会用自己的符号位去补，
 *  而负数的最高位为1，所以补位的数就是1，如果使用>>>则无论如何都用0去补右移后空出来的最高位。

public class BitOperationTest01 {
        
    
    	public static void main(String[] args) {
        
    
    	    /*
    	     * 一个二进制的数要转换成十进制的数的方法是
    	     * 从左至右
    	     */
    	    System.out.println("0011的十进制数是："+Integer.parseInt("0011", 2));
    //		//1、左移：0011   <<  1    =  0110
    	    System.out.println("0011也就是3左移1位后的十进制数是："+(3<<1));
    	    System.out.println("0011左移1位后的十进制数是："+Integer.parseInt("0110", 2));
    	    
    	    //2、带符号位右移：0110  >> 1    =   0011   
    	    System.out.println("0110也就是6带符号右移1位后的二进制数是："+
    	            BitOperationUtils.toBinaryStringHasPreZero(6>>1));
    	    System.out.println("0110也就是6带符号右移1位后的十进制数是："+(6>>1));
    
    	    //不带符号右移：0110>>>1  = 0011
    	    System.out.println("0110也就是6不带符号右移1位后的二进制数是："+
                    BitOperationUtils.toBinaryStringHasPreZero(6>>>1));
            System.out.println("0110也就是6不带符号右移1位后的十进制数是："+(6>>>1));
    	    
    	     System.out.println("0110也就是6带符号右移1位后的二进制数是："+
    	             BitOperationUtils.toBinaryStringHasPreZero(6>>1));
    	    
    	     //32位的二进制：10000000000000000000000000000110   
    	    String numStr = "10000000000000000000000000000110";
    	    numStr = numStr.replace('0', '1');
    	     int tenNum = Integer.parseUnsignedInt(numStr,2);
    	     System.out.println("二进制数的十进制数为："+tenNum);
    	     System.out.println("本身的二进制为："+BitOperationUtils.toBinaryStringHasPreZero(tenNum));
    	     System.out.println("带符号位右移1位后的二进制为："+BitOperationUtils.toBinaryStringHasPreZero(tenNum>>1));
    	     System.out.println("不带符号位右移1位后的二进制为："+BitOperationUtils.toBinaryStringHasPreZero(tenNum>>>1));
    
    	     //-2的32次方到2的32次方-1
    	     System.out.println(Math.pow(2.0, 31));
    
    	    //3、或运算：0011   |    0110   =   0111        凡是有1就为1，二者全为0则为0
    	    System.out.println("0011和0110或运算后的二进制数是："+
    	            BitOperationUtils.toBinaryStringHasPreZero(Integer.parseInt("0011",2) | Integer.parseInt("0110",2)));
    
    
    	    //4、与运算：0011   &    1011   =   0011        凡是有0就为0，二者全为1则为1
            System.out.println("0011和1011与运算后的二进制数是："+
                    BitOperationUtils.toBinaryStringHasPreZero(Integer.parseInt("0011",2) & Integer.parseInt("1011",2)));
    
    
            //5、位运算取反：~ 0011     =   1100           将0变为1，将1变为0
            System.out.println("0011位运算取反后的二进制数是："+
                    BitOperationUtils.toBinaryStringHasPreZero(~Integer.parseInt("0011",2)));
    
            //6、位运算异或：0011 ^ 1011     =   1000      相同为0，不同为1
            System.out.println("0011和1011异或运算后的二进制数是："+
                    BitOperationUtils.toBinaryStringHasPreZero(Integer.parseInt("0011",2) ^ Integer.parseInt("1011",2)));
    	    
    	    
            //对于异或操作，也可以称为“不进位加法”它的高级用法，需要熟记的
            int m = 9,n=10;
            /*
             * m ^ 0  就是和0相同的就是0，和0不同的就是1，
             * 所以结果依然为m
             */
            System.out.println("m异或0后的值为："+(m^0));
            //m ^ 全1的值就是  ~m
            System.out.println("m异或全1后的值为："+(m^~0)+"，m取反的值为："+~m);
            //m ^~m 的值就是全1
            System.out.println("m异或~m后的值为："+(m^~m)+"，全1的值为："+~0);
            //m ^m 的值就是0
            System.out.println("m异或m后的值为："+(m^m));
            
            //交换两个数的位运算写法
    //        int temp = m ^ n;
    //        m ^= temp;
    //        n^=temp;
            m ^= n;
            n^= m;
            m ^= n;
            System.out.println("交换后m的值为："+m+"，n的值为："+n);
            
            
            //num *2 = num << 1  
            
            /*
             * 但是需要注意使用位运算交换两个数组中的数时
             * 如果是两个要交换的数的下标相等那么就会出现错误
             * 现象
             */
            int[] arr = {
        10,10};
            SwapUtils.bitOptSwap(arr,0,1);
            System.out.println("交换后数组为："+Arrays.toString(arr));
            
            
            /*
             * 判断奇偶：
             *  m%2==1  可以转化为：判断m & 1 ==1
             *  m%2==0  可以转化为：判断m & 1 ==0
             */
    
          
           testBitOperation();
    
    	}
    	
    
        /**
         * 位运算测试：某大厂笔试题
         */
        private static void testBitOperation() {
        
            int a=1;
    	    int b=2;
    	    int c=3;
    	    
    	    a |= 4;//a = a | 4  =5
    	    b>>=1;//b 原来的值右移1位后再赋值给b
    	    c<<=1;
    	    a^=c;
    	    //b = 1   c =6   a = 0101 ^ 0110  =15
    	    System.out.println("a="+a+"，b="+b+"，c="+c);
        }
    
    }

### 四、经典面试题 ###

#### 1、处死偶数囚犯面试题 ####

**假如有100名囚犯，需要被处死，但是呢有一个处死的规则：  
将这100名囚犯排站队，从1开始从左至右开始报数  
报数为奇数的枪毙，偶数的存活，然后进入下一轮又重新从1开始报数，  
报数为奇数的枪毙，偶数的存活，直到最后只剩一个囚犯的时候，那个  
囚犯就可以被赦免处死，那么请问如果你是其中的一个囚犯，要不被处死  
最开始应该站到什么位置？**

public class BinaryTest02 {
        
        public static void main(String[] args) {
        
            answer();
        }

/**
         * 答案是应该站到从左至右第64的位置上
         * 将100个囚犯从左至右编号为1至100，
         * 第一轮：1、3、5、7……99号死
         * 第二轮：2、6、10、14……98号死
         * 第三轮：4、12、20、28……100号死
         * 第四轮：8、24、40、56……88号死
         * 第五轮：16、48、80号死
         * 第六轮：32、96号死
         */
        private static void answer() {
        
            List<Integer> arrList = new ArrayList<>();
    
            for (int i = 0; i < 100; i++) {
        
                arrList.add(i + 1);
            }
    
            System.out.println("初始的集合为：" + arrList);
    
            //第一轮
            for (int i = 0; i < 50; i++) {
        
                arrList.remove(i);
            }
            System.out.println("第一轮之后的集合为：" + arrList);
    
            //第二轮
            for (int i = 0; i < 25; i++) {
        
                arrList.remove(i);
            }
            System.out.println("第二轮之后的集合为：" + arrList);
    
            //第三轮
            for (int i = 0; i < 13; i++) {
        
                arrList.remove(i);
            }
            System.out.println("第三轮之后的集合为：" + arrList);
    
            //第四轮
            for (int i = 0; i < 6; i++) {
        
                arrList.remove(i);
            }
            System.out.println("第四轮之后的集合为：" + arrList);
    
            //第五轮
            for (int i = 0; i < 3; i++) {
        
                arrList.remove(i);
            }
    
            System.out.println("第五轮之后的集合为：" + arrList);
    
        }
    }
    
    初始的集合为：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
    第一轮之后的集合为：[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100]
    第二轮之后的集合为：[4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100]
    第三轮之后的集合为：[8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96]
    第四轮之后的集合为：[16, 32, 48, 64, 80, 96]
    第五轮之后的集合为：[32, 64, 96]
    Process finished with exit code 0

#### 2、老鼠试药问题： ####

老鼠试药问题：  
**说有100瓶药水，其中有一瓶是毒药可以在老鼠  
服用后1周后将其毒死，其余的药水则和清水的效果一致  
老鼠服用后不会有任何生命危险，毒药和无毒药水在外观上  
无法区分，并且只能通过老鼠试药水的方式才能确定哪一瓶  
是有毒的药水。那么请问在1周时间内最少需要多少只老鼠  
可以将这瓶有毒的药水找到？**

/**
         * 答案是最少需要7只老鼠
         * 将100瓶药水分别编号为1至100，然后分别用二进制
         * 表示为：
         *  1号：     0000001
         *  2号：    0000010
         *  3号：    0000011
         *  ……
         *  100号：1100100
         *  
         *  给老鼠也按照1至7编好号，然后
         *  然后让1号老鼠分别喝下最高位为1的号数的药水，
         *  2号老鼠分别喝下第二高位为1的号数的药水，
         *  ……
         *  7号老鼠分别喝下最低位为1的号数的药水
         *  一周后观察老鼠的死亡情况，假设死亡的老鼠为
         *  1号、4号、7号
         *  那么最终有毒的药水就为：1001001
         */
        private static void answer() {
        
            System.out.println(Integer.toBinaryString(10000));
            System.out.println("最终有毒的药水编号为："+Integer.parseInt("1001001", 2));
        }
    
    }
    10011100010000
    最终有毒的药水编号为：73