学习
实践
活动
工具
TVP
写文章
专栏首页MyJava算法(十) 位运算

算法(十) 位运算

&按位与

只有1&1= 1

有0一定为0。

  • n&n-1 可是使得n最靠后的1变成0,其他位置不变。
  • 在快速幂这种,比较个位数与1。如1001 & 1。当个位是1的时候输出1。

|按位或

只有 0|0 = 0

可活用在让一个数据的某些位置变1。

^按位异或

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

三个性质

  • 0^X = X; X^X =0
  • 交换律 :a^b = b^a
  • 结合律:a^b^c = a^(b^c)

使特定位置翻转。例:X=10101110,使X低4位翻转,用X ^ 0000 1111 = 1010 0001即可得到。

~取反

~1=0; ~0=1;

使一个数的最低位为零,可以表示为:a&~1。

~1的值为1111111111111110,再按“与”运算,最低位一定为0。

<< 左移运算符

相当于*2。

>>右移运算符

相当于/2。

>>> 和 <<< 无符号整数的右移和左移运算符

就是无视符号位,把符号位当成数值位移动。

计算机中表达数都是用有符号整数,所以当做到无符号整数的题目时,移动一定要用这两运算符。

1,应用算法

快速幂

计算x的n次方的时候,常见方法是x乘n次,这种方法的时间复杂度是0(n)。

而快速幂是利用了位运算,比如2的10次方,将10转换成1001,为1的时候要乘以权重,这样只要乘3次。

快速幂的时间复杂度为0(logn)。

1,题目

2,解法

class Solution {
    public double myPow(double x, int n) {
        if(x == 0 || n == 0 || x==1)
            return 1;
        long cur = n;
        if( cur<0 ){
            x = 1/x;
            cur = -cur;
        }
        double ans = 1.0;
        while(cur>0){
            if((cur & 1) == 1){
                ans *= x;
              
            }
            x *= x;
            cur>>=1;
        }
        return ans;
    }
}

需要注意n等于-(2的32次方)。如果没有将n转成long型的话,直接-n就会大于int的最大值(2的32次方-1)。

位运算需要修改符号的,最好还是换成大的整数结构。

public int myPow(double x, int n) {
        int a = -2147483648;
        return -a;
    }

最后结果本应该为2147483648,但是给出的结果是a,溢出就没有处理。

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.syjhxy.ltd/复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 算法:位运算

    •反码:正数的反码就是原码,负数的反码是符号位不变,其余位取反(对应正数按位取反)

    用户3578099
  • 【算法技巧】位运算指南

    位算法的效率有多快我就不说,不信你可以去用 10 亿个数据模拟一下,今天给大家讲一讲位运算的一些经典例子。不过,最重要的不是看懂了这些例子就好,而是要在以后多去...

    Java团长
  • 基础算法篇——位运算

    秋落雨微凉
  • 按十进制位与运算

    方法1:对程序员来说最简单的是,让游戏策划把所有5级装备都配置在表格里,他们的解锁关卡都是10234567;

    用户1396155
  • 算法篇:位运算基本操作

    https://leetcode-cn.com/problems/number-of-1-bits/

    灰子学技术
  • ACM算法竞赛——位运算(模板)

    程序中的所有数在计算机内存中都是以二进制的形式存储的。位运算就是直接对整数在内存中的二进制位进行操作

    战士小小白
  • 算法篇:位运算进阶(二)

    转换成前面算法篇:位运算异或的使用(一)中,两位相同的数异或为0,转换成3位数的"异或"操作位0,也就是说我们需要实现同一个bit位的3个1,操作为0就可以,将...

    灰子学技术
  • 【算法技巧】位运算装逼指南

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 位运算和十转二进制

    前两天做C语言二级模拟题,发现其中涉及到了一部分位运算的题目,但是自己从来没去学过,于是就抽时间了解了一下。并编成了c程序方便自己了解,但是在进行位运算的时候还...

    布衣者
  • 位运算

    将两个十进制数转为二进制,将此两个二进制转换为列竖式,运算时两个位数任意一个是0则此位是0,有1个1则是1。然后将结果转为十进制。

    收心
  • 位运算

    ​ 任何信息在计算机中都是采用二进制表示的,数据在计算机中是以补码形式存储的,位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作,...

    fishhh
  • 位运算

    From Zero
  • 位运算

    用户3004328
  • 位运算

    取反是一元运算符,对一个二进制数的每一位执行逻辑反操作。使数字1成为0,0成为1。

    Helloted
  • 位运算

    &运算通常用于二进制取位操作,例如一个数 & 1 的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最末位为 0 表示该数为偶数,最末位为 1 ...

    Cell
  • 位运算

    位运算   位运算是把数字用二进制表示之后,对每一位上0或者1的运算。   理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者1.比如十进制的2转...

    猿人谷
  • LeetCode-算法-位运算-第14天

    思路:for i in range(0,32)表示循环次数32次。(n&1)之前了解过,只保留当前n最右侧一位,(n&1)<<(31-i),的意思是将最右侧一位...

    布衣者
  • LeetCode-算法-位运算-第13天

    给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。 如果存在一个整数 x 使得 n == 2x ,则认为...

    布衣者
  • 一道位运算的算法题

    一组整数,除了一个只出现一次以外,其他每个整数都恰好出现三次,要寻找那个特殊的整数。

    四火

扫码关注腾讯云开发者

领取腾讯云代金券