位与进制

位运算简介

 这里我假设读者有二进制的思维,知道(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:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术沉淀

Python: 函数式编程

map()函数接收两个参数,一个是函数,一个是序列,map将传入的函数依次作用到序列的每个元素,并把结果作为新的list返回,比循环更简洁,更易读。

18440
来自专栏数据结构与算法

codevs 4163 hzwer与逆序对

 时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description hzwer在研究逆序对。 对于数...

32480
来自专栏web前端教室

js数组去重的思路与缓动公式

前端开发的面试中,至少有一类题是必出的,那就是去重。什么叫去重呢?就是把一组字符串中重复出现的,都删除掉。 这种题重要的是解决的思路要正确,思路正确的话其实也很...

24980
来自专栏Bingo的深度学习杂货店

Q38 Count and Say

The count-and-say sequence is the sequence of integers with the first five terms...

36570
来自专栏chenjx85的技术专栏

leetcode-344-Reverse String

24450
来自专栏数据结构与算法

P3373 【模板】线段树 2 区间求和 区间乘 区间加

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输...

419110
来自专栏小小挖掘机

各种排序算法的分析及java&python实现

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

40870
来自专栏Python爬虫与算法进阶

Leetcode-Solutions 1.two-sum (Python&Golang)

恩,最后找队友一起刷题。喜欢可以联系我 ,来公众号“Python爬虫与算法进阶”找我哦

42390
来自专栏积累沉淀

JavaScript面向对象与原型

javaScript有两种开发模式:1.函数式(过程化),2.面向对象(OOP)。面向对象的语言有一个标志,那就是类的概念,而通过类可以创建任意多个具有相同属性...

255100
来自专栏技术沉淀

Numpy 求100以内质数和

17850

扫码关注云+社区

领取腾讯云代金券