MENU

位与进制

July 28, 2018 • Read: 196 • 算法

位运算简介

这里我假设读者有二进制的思维,知道$(3)_{10}=(011)_2$将十进制转换为二进制的方法

  • &(与)、|(或)、^(异或)、~(非/取反)
  • >>和<<运算符将二进制位进行右移或者左移操作
  • >>>运算符将用0填充高位;>>运算符用符号位填充高位,没有<<<运算符
  • 对于int型,1<<35与1<<3是相同的,左边的操作数是int的时需对右侧操作数模32,而左边的操作数是long型时需对右侧操作数模64

关于上面的说明,这里还是补充一下,因为并不是所有人都了解位运算

<<的运算规则:按二进制形式把所有的数字向左移动对应的位数,高位移出(舍弃),低位的空位补零。以3<<2为例,首先把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011(int型是4个字节,1个字节8位,所以int是32位),然后将上面的二进制数字向左移动2位后面补0得到0000 0000 0000 0000 0000 0000 0000 1100

在数字没有溢出的前提下,对于正数和负数,左移一位都相当于乘以2的1次方,左移n位就相当于乘以$2^n$

>>的运算规则:按二进制形式把所有的数字向右移动对应位数,低为移出(舍弃),高位的空位补符号位,即正数补零,负数补1.以11>>2为例,首先把11转换为二进制数字0000 0000 0000 0000 0000 0000 0000 1011,然后把低位的两个数字移出,因为该数字是正数,所以在高位补零,则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010

右移一位相当于除以2,右移n位相当于除以$2^n$

>>>运算规则:和>>大致相同,区别在于不论是正数还是负数,高位都补零

位运算的奇巧淫技

  • 判断奇偶位(x & 1 == 1?奇:偶)
  • 获取二进制位是1还是0
  • 交换两个整数变量的值(t = a ^ b;a ^= t;b ^= t;)
  • 不用判断语句,求整数的绝对值(a ^ (a >> 31)) + (a >>> 31)
  • 结合律 (a^b)^c==a^(b^c)
  • 对于任何数x,都有x^x=0,x^0=x,同自己求异或为0,同0求异或为自己
  • 自反性a^b^b=a^0=a,连续和同一个因子做异或,最终结果为自己

题1:找出唯一成对的数

1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素重复,其它均只出现一次,每个数组元素只能访问一次,设计一个算法,将它找出来,不用辅助存储空间

题解

位运算总共就那么几条性质,假设一个数组中的值分别是1,2,3,4,2,2是重复的元素,那么应该怎么把它挑出来呢,最开始想到的方法肯定是两重循环枚举,时间复杂度是O($n^2$),不太好,想想怎么用位运算解决这道题,根据a^a=0,a^0=a这两条性质,我们可以把数组中的元素全部异或起来,然后再异或一遍不重复的所有元素,就是(1^2^3^4^2)^(1^2^3^4),这样把它们凑起来,最后结果就应该是2^2^2=2^0=2,正好是要找的重复元素

代码
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = 1001,sum1 = 0,sum2 = 0;
        int[] arr = new int[n];
        for(int i = 0;i < n - 1;i++) {
            arr[i] = i + 1;
            sum1 ^= arr[i];
        }
        arr[n - 1] = new Random().nextInt(n);//随机数,1-n
        sum2 = sum1 ^ arr[n - 1];
        int idx = new Random().nextInt(n);//随机选取一个下标
        {//交换
            int t = arr[idx];
            arr[idx] = arr[n - 1];
            arr[n - 1] = t;
        }
        /*for(int i = 0;i < n;i++) {
            System.out.print(arr[i] + " ");
        }*/
        System.out.println(sum1 ^ sum2);
    }
}

题2:找出落单的数

一个数组里除了某一个数字以外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字

题解

这道题比上一道题还简单,这道题直接将所有的值全部异或起来,得到的结果就是落单的数了

题3:二进制中1的个数

请实现一个函数,输入一个整数,输出该二进制表示中1的个数

题解

第一种方法:假设这个数是3,其二进制为011,首先将011&001,判断得出来的结果是否等于001,如果等于,说明这个第1位是1;然后将011&010,判断得出来的结果是否等于010,如果等于,说明这个第2位是1,一直进行下去,判断31位

代码
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int cnt = 0;
        for(int i = 0;i < 32;i++) 
            if(((1 << i) & n) == (1 << i))
                cnt++;
        System.out.println(cnt);
    }
}
第二种方法

第二种方法:只让要测验的数向右移。假设这个数是3,其二进制为011,首先将011&001,判断得出来的结果是否等于001,如果等于,说明这个第1位是1;然后将001&001,判断得出来的结果是否等于001,如果等于,说明这个第2位是1,一直进行下去,判断31位

代码
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int cnt = 0;
        for(int i = 0;i < 32;i++) 
            if(((n >>> i) & 1) == 1)
                cnt++;
        System.out.println(cnt);
    }
}
第三种方法

第三种方法:还是假设这个数是3,那我们让3变成0的过程中肯定是要消掉1的,消掉多少次1,就表示3的二进制中有多少个1。关键就在于,如何消掉011中的1,我们首先让011减1,那么011就变成了010,然后让011&010,就得到了010,然后再让010减1,那么010就变成了001,然后让010&001,就得到了000,转换成伪代码的形式就是,a = (a - 1) & a,它的效果就是消掉最低位上的1,依次消掉所有最低位上的1,最后不久变成了0吗

代码
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int cnt = 0;
        while(n != 0) {
            n = (n - 1) & n;
            cnt++;
        }
        System.out.println(cnt);
    }
}

题4:是不是2的整数次方

用一条语句判断一个整数是不是2的整数次方

题解

这道题比较好想,判断一个数是不是2的整数次方,其实就是判断这个数的二进制数是不是有且仅有一个1,这个和上面那道题很相似,仔细想想,直接给出代码了

代码
if((n & (n - 1)) == 0)

题5:将整数的奇偶位互换

假设这个数是9,二进制就是1001,那么得到的结果就是0110

题解

首先我们需要两个个数

a = 0x55555555
b = 0xaaaaaaaa

a和b都是16进制数,转换为二进制分别是0101 0101 0101...,1010 1010 1010...(因为1010对应的十进制是10,而10在16进制中是a,0101也同理),然后将需要改变的数n分别对a和b进行&运算得到c和d,然后将c向左移1位,将d向右移1位,再分别进行异或,就得到所求结果,看下面示例

n = 1001
a = 0101
b = 1010
c = n & a = 0001
d = n & b = 1000
res = (c << 1) ^ (d >> 1) = 0110

题6:0-1间浮点实数的二进制表示

给定一个介于0和1之间的实数,(如0.625),类型为double,打印他的二进制表示(0.101),如果该数字无法精确地用32位以内地二进制表示,则打印“ERROR”

代码
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        double num = cin.nextDouble();
        StringBuilder sb = new StringBuilder("0.");
        while(num > 0) {
            double r = num * 2;
            if(r >= 1) {
                num = r - 1;
                sb.append("1");
            } else {
                num = r;
                sb.append("0");
            }
        }
        if(sb.length() > 34) 
            System.out.println("ERROR");
        else
            System.out.println(sb.toString());
    }
}

题7:出现k次和出现1次的数

数组中只有一个数出现了1次,其他的数都出现了k次,请输出出现了1次的数

题解

这道题有很多种做法,但是这里我们只考虑如何利用进制的方法去做,多的也不说,大家只要记住一个结论k个相同的k进制数做不进位加法结果为0。举个例子,3个相同的三进制数,假设个这个数是2,2的三进制是011,所以三个011做不进位加法结果就是011+011+011=000;再比方说10个十进制数相加,假设这个数是10,做不进位加法最后结果也是0

代码
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int[] arr = {3,3,3,5,7,7,7,8,8,8,6,6,6};
        int len = arr.length;
        char[][] kRadix = new char[len][];
        int k = 3;
        int maxlen = 0;
        //转换成k进制字符数组
        //对于每个数字
        for(int i = 0;i < len;i++) {
            kRadix[i] = new StringBuilder(Integer.toString(arr[i],k)).reverse().toString().toCharArray();
            if(maxlen < kRadix[i].length)
                maxlen = kRadix[i].length;
        }
        int[] resArr = new int[maxlen];
        for(int i = 0;i < len;i++) {
            //不进位加法
            for(int j = 0;j < maxlen;j++) {
                if(j > kRadix[i].length) 
                    resArr[j] += 0;
                else 
                    resArr[j] += (kRadix[i][j] - '0');
            }
        }
        int res = 0;
        for(int i = 0;i < maxlen;i++) 
            res += (resArr[i] % k) * (int)(Math.pow(k,i));
        System.out.println(res);
    }
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code