[Java 泥水匠] Java Components 之二:算法篇之项目实践中的位运算符(有你不懂的哦)-阿里云开发者社区

开发者社区> 人工智能> 正文

[Java 泥水匠] Java Components 之二:算法篇之项目实践中的位运算符(有你不懂的哦)

简介:

2.1 前言

  自从上篇[Java 泥水匠] Java Components 之一:Java String (肯定有你不懂的泥瓦匠很快又和你们聊起来了。写的还不错~

K8(O$H_5I1$I%QZVNXHY]M6

要时刻对自己说:

得到殊荣也是昨天,看在眼里的只有今天。等待明天的只有死亡和坟墓。

回到正题,今天是讲位运算的,肯定有你不知道的。
提纲:

  • 2.2    异或基本算法
  • 2.2.1  补充例子异或加密解密
  • 2.3   ‘按位与’运算 就是那么简单
  • 2.4    从非中,学习原码补码运算
  • 2.5    综合算法现实案例
  • 2.6    总结

2.2 异或基本算法

  看题目顾名思义,泥瓦匠要跟你们聊聊这位运算。怎么聊法,依旧和老套。师傅出招棋盘上马,你徒弟怎么对答,然后周而复始。你就青出于蓝了。很早的时候在一本《算法竞赛入门经典》,有些acmer应该知道的。原题目很简单,是这样的:
两个变量A,B如何交换。
“泥瓦匠,你找抽。定个temp不就搞定了。”骂声将至,我赶紧说,除了这个方法,还有下面这个:

1
2
3
4
5
6
<font face="宋体" size="4">A = A + B;
 
B = A –B;
 
A = A - B;
</font>

  这样子,我们不可全盘否认,在多数情况下,还是能达到目的的。但是问题就来了,这样做为什么不行呢。我们考虑下,一个是这试用的范围很小,不满足全部类型数据。二个是这个会越界,越界导致我们算法和程序会bug或者无法进行。
  又看看题目,聪明的小伙伴兴许想到了:

1
2
3
4
5
6
7
8
<font face="宋体" size="4">private static void test1()
    {
        int A = 11;
        int B = 222;
        A = A ^ B;
        B = A ^ B;
        A = A ^ B;
    }</font>

看着上面这个运算是CPU位运算,所以效率极高,也不会越界。在计算机系统中大量存在,可以反向规则恢复数据本身。这时候有些小伙伴不懂,泥瓦匠就补下异或的知识吧。

  异或运算,是按照二进制位进行。异或运算的规则是0⊕0=0,0⊕1=1,1⊕0=1,1⊕1=0。“泥瓦匠,这个也太烦了吧,记公式我最不行了。”别怕,泥瓦匠有高招。这个也是来自前人,古人的武功秘籍。不是吗什么易筋经,什么少林武学。哈哈,太极啊,书法啊,要那个灵性,技巧。哈哈,泥瓦匠喜欢书法,喜欢的可以交流。
  记忆宫殿
异或异或,又称半加法运算。例如,1⊕1可以当成二进下,1+1=10然后取最后一位,正好是异或的结果,0+0、1+1、0+1同理。这只是前人流传下来的记忆方法。

2.2.1 补充例子异或加密解密

  泥瓦匠就在补充个例子,利用抑或算法进行加密解密。这是种简单加密,但是也有它的优势:速度快,长数据的一般加密任务很适合。不多说,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* encrypt using the exclusive or*/
    private static void test2(String str)
    {
        byte key = 123;
        byte strByte[] = str.getBytes();
         
        /* encrypt */
        for (int i = 0; i < strByte.length; i++)
        {
            strByte[i] = (byte) (strByte[i] ^ key);
        }
             
        System.out.println("加密后:" + new String(strByte));
         
        /* decrypt */
        for (int i = 0; i < strByte.length; i++)
        {
            strByte[i] = (byte) (strByte[i] ^ key);
        }
         
        System.out.println("解密后:" + new String(strByte));
    }

  我们测试下 test2("13958686678");,然后在控制台可以清楚的看出加密后和解密后的状态:

image

  总结:加密解密的操作方式一样,这个加密不怎么棒,而且一看数据都是对应的AABBCC型。但加密后的数据也可以进行存储或网络传输。如果有不需要很大安全性的,但是数据有长要求速度和效率的可以尝试下哦

2.3 ‘按位与’运算 就是那么简单

  下面泥瓦匠要讲这个&了。上面讲了异或,下面我就讲讲这个,在很人眼里仿佛和异或有着某种,或是对立或是啥的关系的按位与运算符。其实没有,他们 只是在CPU级别的,一些门电路设计下的规律而已。哈哈,虽然学过电子技术,但经常逃课,还挂科了,泥瓦匠也就不显摆我电子技术多牛逼了。举个例子吧:

1
2
3
4
5
6
    private static void test3()
{
    int a = 6550; //    1100110010110
    a = a & 255;  //         11111111
    System.out.println(a);// 10010110
}

  例子中,看了注释有些人懂了。其实例子很简单,就是一个数字截取二进制下从低到高的8位。和上面的一样,这运算符广泛的运用在系统内部。效率极高,但我们 也可以在某种算法中去。比如我现在想要6550的二进制的不要二进制下从低到高的8位,那样你是否马上就能写出。只要把255改成(65535 - 255),然后右移8位即可呢?为什么是这个两个数字呢,泥瓦匠告诉你转化成二进制你就明白了。

  按位与运算与(AND):对两个整型操作数中对应位执行布尔代数,两个位都为1时输出1,否则0。
  这也没什么记忆技巧,一与一,唱着歌谣记下去。

2.4 从非中,学习原码补码运算

  累了累了,先去玩一会,再看下面很枯燥的东西吧。我推荐番茄工作法。25分钟。

  下面泥瓦匠和你们一起学习这个枯燥的东西。要学习原码补码运算。首先得知道一些基础的东西:机器数和真值。所谓的机器数就是,一个数在计算机中的二进制形 式。机器数时代符号的,在计算机用一个数的最高位存放符号。正数为0,负数为1。那什么叫真值呢?真值其实就是实际值,因为最高位的0或者1会导致形式上 的有变,就像 1000 0011 表示机器数,它的真值为 –3 或者 -000 0001。哈哈?泥瓦匠这个太简单的。对,什么事情都是简单到复杂。简单的事情做多了就成大事了。

  而原码, 反码, 补码是机器存储一个具体数字的编码方式。下面简单介绍这三个:
  原码是人最容易理解和计算的表达式。第一位表示符号,后面的表示值。0为正值,1为负值。
  反码,顾名思义,和原码有关系。有时候,一个反码表示负数,我们无法将其计算。可以转换为原码在计算。反码的计算方法如下:

      正数的反码是其本身

      负数的反码是在其原码的基础上, 符号位不变,其余各个位取反.

  补码的表达方式也如下:

      正数的补码就是其本身

      负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

 

  “我去,泥瓦匠,头晕了。哈哈累了累了。慢慢来”

   为什么要用这些呢。我的建议先死背,然后用领会。因为计算机里面最基础的运算需要他们帮助计算机完成。因为一个符号位正负会让基础电路设计很复杂。所以就想出来用符号位参与运算。反码,补码是用来计算用的。下面举个简单的例子。首先是反码计算十进制的表达式: 1-1=0。下面摘自网络大牛结论:

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

发现用反码计算减法, 结果的真值部分是正确的. 而唯一的问题其实就出现在"0"这个特殊的数值上. 虽然人们理解上+0和-0是一样的, 但是0带符号是没有任何意义的. 而且会有[0000 0000]和[1000 0000]两个编码表示0.

于是补码的出现, 解决了0的符号以及两个编码的问题:

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

这样0用[0000 0000]表示, 而以前出现问题的-0则不存在了.而且可以用[1000 0000]表示-128:

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

-1-127的结果应该是-128, 在用补码运算的结果中, [1000 0000] 就是-128. 但是注意因为实际上是使用以前的-0的补码来表示-128, 所以-128并没有原码和反码表示.(对-128的补码表示[1000 0000]补算出来的原码是[0000 0000], 这是不正确的)

使用补码, 不仅仅修复了0的符号以及存在两个编码的问题, 而且还能够多表示一个最低数. 这就是为什么8位二进制, 使用原码或反码表示的范围为[-127, +127], 而使用补码表示的范围为[-128, 127].

因为机器使用补码, 所以对于编程中常用到的32位int类型, 可以表示范围是: [-231, 231-1] 因为第一位表示的是符号位.而使用补码表示时又可以多保存一个最小值.

深呼吸,还有关于现实例子的算法。加油泥瓦匠~

2.5 综合算法现实案例

  最后一个综合性算法例子,泥瓦匠就结束这篇位运算的文章。泥瓦匠都口水讲完了。看吧看吧,一起看。

  业务系统中,我们会发现大量的判定是否。以int数据为例子,如果按照十进制的方式存储数据,一个32位的int变量只能存储一个数值,而如果使用二进制 方式存储数据(缺点是只能存储0或1两个数据)则可以存储32个数据,将极大的节约内存。利用位运算存储数据,主要是为了减少程序占用的内存。这样的设计 是没有错的,但是如何操作呢?哈哈,泥瓦匠也不卖关子了。当然是位运算。但有些同学用什么toBinary转来转去,都不知道这样的操作复杂度很高,导致 得不偿失。

所以设计好了,实现更重要

  例如,在一个int变量的从右侧开始倒数第5位存储数据,则存储和读取数据的代码如下所示: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void test4()
    {
        //在一个int变量的从右侧开始倒数第5位存储数据
        int bData = 0;
         
        bData = bData | (1 << (5 - 1));    //存储数值1
        System.out.println(bData);
         
        bData = bData & (~(1 << (5 - 1))); //存储数值0
        System.out.println(bData);
            
        int n = bData & (1 << (5 - 1));    //读取数据  
        System.out.println(n);
    }

  例子可以看出,我们成功的把5位的1和0互换。这就代表着一个是否的是否状态。所以泥瓦匠想说的是,考虑int的位而不是表面的意义能创造更多财富。财富来源于细节。和武学一样,最高境界就是 无形。但是要从有形来,组合的有形深不可测。就像这个综合案例一样。

    精髓:掌握到底层的妙用,方能成就高层建筑。

 

2.6 总结

  组合拳的组合的有形深不可测。就像这个综合案例一样。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章