反码补码和位运算


看集合扩容时能经常看到位运算,所以翻出来复习一下

1. 原码,补码,反码

  • 原码:将数值转化成二进制,最高位表示符号位
  • 反码:在原码的基础上,正数不变、负数符号位不变,其余各位取反
  • 补码:在原码的基础上,正数不变、负数符号位不变,其余各位取反再加1(即反码+1)

三者是计算机存储数据的不同形式,计算机用补码存储数据。而且计算机利用这三者可以用加法实现减法

反码:

1+(-1) = [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0

反码出现了 [0000 0000] 原和 [1000 0000] 原两个编码表示正负0,补码出现了

补码:

1+(-1) = [0000 0001]补 + [1111 1111]补 = [0000 0000]补 = [0000 0000]原

解决了正负0编码不同问题

2. 位运算

位运算是对底层2进制操作的

符号

描述

运算规则

&

两个都为1,结果才为1

|

两个都为0,结果才是0

^

异或

同0异1

~

取反

0变1,1变0

<<

左移

各二进位全部左移若干位,高位丢弃,低位补0。表示2次幂

>>

右移

各二进位全部右移若干位,对无符号数,高位补0。表示除2

有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)

>>>

逻辑右移

不管符号位,直接右移,补零

3. 实际操作

判断奇偶

// 最末尾为0偶数,1奇数
// 转成二进制,eg:1010 = 2^3 + 0 + 2^1 + 0 = 10偶数,只看最后一位即可因为,2^0 = 1,不是2的倍数
public static void main(String[] args) throws IOException {

    int a = 4;
    if( (a & 1) == 0){
        System.out.println("偶数");
    }else{
        System.out.println("奇数");
    }
}

取模

h & (length-1)
    
// 其实很简单,主要看length
// &运算,就算h全部为1,&之后都是看length有1的部分,高位全为0
// 那么最大只能是length,所以范围限定在了length里,比 % 运算快多了
// -1为了符合数组0开始
// 这也是扩容为2次幂的原因,配合取模运算

2次幂(只有一个1,其他位为0)

1---0001
2---0010
4---0100
8---1000

快速幂

int poww(int a,int b){
    int res = 1;
    int base = a;
    
    while(b != 0){
        if( b & 1 != 0){	// 找到二进制尾数为1的
            res *= base;	// 结果乘于幂
        }
        base *= base;		// 这里呢,一直乘,模拟次幂递增,如果上面为1了,那么这样就会对应到乘于几次幂
        b >>= 1;
    }
    return res;
}

位运算加法

public int Add(int num1,int num2) {
        
    while(num2 != 0){
        int sum = num1 ^ num2;  // 计算有单个1的位(0和0位不用计算了,1和1进位给下面操作了)
        int carry = (num1 & num2) << 1;  // 进位操作
        num1 = sum;
        num2 = carry;
    }
    return num1;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer-2

    晚上没宵夜
  • Java的标签

    以前笔者如何退出双重循环呢? 利用循环条件判断,加上break、continue、return可以改变流程

    晚上没宵夜
  • 小根堆的Java实现

    堆是完全二叉树的数组形式,由于堆没有指针指向,所以可以利用下标来模拟指向,假设 i 为父节点,那么 2i+1 为左孩子,2i+2 为右孩子。假设 i 为当前节点...

    晚上没宵夜
  • 浅谈我对动态规划的一点理解---大家准备好小板凳,我要开始吹牛皮了~~~

    前言 作为一个退役狗跟大家扯这些东西,感觉确实有点。。。但是,针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚,我决定还是拿出我的全部家当,来跟大家分...

    Angel_Kitty
  • Wannafly挑战赛27

    给出长度为n的序列a, 求有多少对数对 (i, j) (1 <= i < j <= n) 满足 ai + aj 为完全平方数。

    xiaohejun
  • 照片处理-几何滤镜实现哈哈镜

    几何滤镜比较简单,不涉及色彩模型,按照某种算法,对原图进行采样,得到一张新的图片。看起来就像是把原图进行了几何变形。 这篇文章通过两个简单的案例,更直观的感受...

    用户1068165
  • 绿豆蛙的归宿 期望dp+拓扑排序

    f[ x ] = sigema( f[ y ] + w(x,y)  )/out[ x ];

    用户2965768
  • 【USACO 2.4 】Bessie Come Home

    饶文津
  • #define a int[10]与 typedef int a[10]用法

    Daotin
  • LeetCode 310. 最小高度树(图 聪明的BFS,从外向内包围)

    对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券