鱼C论坛

 找回密码
 立即注册
查看: 3009|回复: 0

[好文转载] 位运算的妙用

[复制链接]
发表于 2017-1-20 23:49:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 零度非安全 于 2017-1-21 11:23 编辑
来源:赖信涛
链接:kawabangga.com/posts/284

最近在学 java,其实仅仅是在命令行里写程序跟 C 语言没有太大的区别,思想都是一样的。遇到了一个比较新鲜(后来知道原来 C 中也有)的东西——位元算(又叫位操作)。多新鲜啊,毕向东老师说这次(现在正在学习的这次)使用位元算符将会是你们今后使用的唯一的一次,因为在开发中根本用不着。其实也差不多。不过见到了几个应用,还是蛮有意思的,这里总结一下(万一考试就考到了呢,呵呵)。

Java中共有7个位运算符:~(取反)、&(与)、|(或)、^(异或)、>>(右移)、<<(左移)、>>>(无符号右移)。这里不在解释位运算,只是谈谈几种位运算的有趣用法。

加密

1 一个数异或同一个数两次还是原数;

2 计算机中的文件都是以二进制的形式来存储的;

利用这两个特性,我们就可以用 ^ 运算来给文件加密。例如将一个二进制文件中所有的数据都异或 42 这个数字,就得到了一个加密后的文件,“42”就是这个文件的“钥匙”。将这个文件中的所有数据再异或 42,就完成了“解密”的过程。

不增加新的变量来交换 a,b 两个变量的值


交换 a,b 两个变量的值,几乎是每一个人在学编程的时候都要接触的。现在我们想这个问题,我有两个瓶子,A 瓶装着果汁,B 瓶装着醋,要是 A 瓶装醋,B 瓶装果汁,如何做呢?通常,我们会用下面这段代码:
  1. int temp;

  2. temp = a;
  3. a = b;
  4. b = temp;
复制代码

这就像我们找来一个新瓶子 C,先将果汁倒入新瓶子,然后醋倒入 A,果汁再倒入 B。这是很容易想到的办法。那么如果没有别的瓶子了呢?看看这个:
  1. a = a + b; //此时a包含a 和 b
  2. b = a - b;
  3. a = a - b;
复制代码

只有两个瓶子,那么我们只好把它们倒在一起,然后将混合物中的果汁倒入 B。不可思议是吗?别急,我们将果汁和醋倒在一起的时候,B 瓶还在,这可是程序呀,B 瓶仍然装着醋,这时我们就可以将(混合-醋)的值给 B,也就是果汁,再将(混合-果汁)的值给 A,完成!但是,这种方式有一个弊端:有可能 a+b 的值会超出 int 型的范围。

基于同样的想法,我们还可以用一下的代码:
  1. a = a ^ b;
  2. b = a ^ b;  //实际上是(a^b)^b 也就是a异或了b两次,等号右边是a的值
  3. a = a ^ b;  //此时b里面已经是“果汁”,实际上是(a^b)^a,也就是b异或了a两次,是b
复制代码

第一步之后,原来a占用了多少位依旧是多少位,绝对不会发生数据的溢出。

ps:为了程序的可读性,真正开发时要慎用后两种!

进制的转换(10进制转16进制为例)

接触位运算之前,进制转换我是这么操作的:
  1. class turn10_16{
  2.         public static void main(String[] args){
  3.                 int n = 200;                      //n就是待转换的数字
  4.                 boolean out_turn = false;         //输出时用,去掉出时时候高位的'0'
  5.                 int[] s = new int[20];            //将转换肉的十六进制数存放在s[]数组中               
  6.                 while(n > 10){
  7.                         int i = 0;
  8.                         s[i]++;
  9.                         while(s[i] > 15){         //逢16进1,并且检查下一位
  10.                                                   //是不是16,如果是,再进一
  11.                                 s[i] = 0;
  12.                                 i++;
  13.                                 s[i]++;
  14.                         }
  15.                         n--;                      //数完一个之后--,知道数完n个数
  16.                 }        
  17.                 for(int i = 19;i >= 0;i--){
  18.                         if(out_turn == false){    //这个if是为了去掉最高位上的0
  19.                                                   //其中out_turn作为开关
  20.                                 if(s[i] == 0){
  21.                                         continue;
  22.                                 }
  23.                                 else{
  24.                                         out_turn = true;
  25.                                         i++;
  26.                                 }
  27.                         }
  28.                         else{                     //输出转换之后的结果,10输出A,类推
  29.                                 if(s[i] < 10){
  30.                                         System.out.println(s[i]);
  31.                                 }
  32.                                 else{
  33.                                         System.out.println((char)('A' + (s[i] - 10)));
  34.                                 }
  35.                         }
  36.                 }
  37.                 System.out.println();
  38.         }
  39. }
复制代码

这种转换就像数数,一共有多少个,我来用十六进制的方法再数一遍,逢 16 进 1,数完为止。这种方法的弊端就是效率低,而且不能转换负数。

我们知道,10 进制的数据在计算机中使用2进制来存储的,而 16 进制的出现也是为了阅读性强,使4个位置放在一起计数。那么理论上,用“位运算”来操作,效率肯定会高。
  1. class turn10_16{
  2.         public static void main(String[] args){               
  3.         int n=200;                                //n就是代转换的数字
  4.         boolean out_turn=false;                   //输出时用,去掉输出时候高位上的‘0’
  5.         int[] s=new int[20];                      //将转换后的十六进制数存放在s[]数组中
  6.         for(int i=0;i<=8;i++){                    //int型占用了8个byte位置,每个byte即一个16进制,
  7.                                                   //每次保留一个byte并且转换成16进制,至少要8次(可以优化)
  8.             int temp= n & 15;                     //与0000-0000 0000-0000 0000-0000 0000-1111进
  9.                                                   //行&运算,只保留最后4个位置即“个位”上的数
  10.             s[i]=temp;                            //将这个数赋给个位
  11.             n=n>>>4;                              //无符号右移4个位置,再保留出十位上的数
  12.         }
  13.         for(int i=19;i>=0;i--){
  14.             if(out_turn == false){                //这个if是为了去掉最高位上的0,其中out_turn作为
  15.                                                   //开关;
  16.                 if(s[i]==0)
  17.                     continue;
  18.                 else{
  19.                     out_turn=true;
  20.                     i++;
  21.                 }
  22.             }
  23.             else{                                //输出转换之后的结果,10输出A,类推
  24.                 if(s[i]<10)
  25.                     System.out.print(s[i]);
  26.                 else
  27.                     System.out.print((char)('A'+(s[i]-10)));
  28.             }
  29.         }
  30.         System.out.println();
  31.     }
  32. }
复制代码

总结:如此看来,位元算还是很有必要学习的。基于计算机只认识 0 和 1,很多关于内存的操作用位运算效率会提高不少,毕竟我们是与计算机打交道。像  *2/2 运算、取绝对值运算,取相反数运算等等,直接对内存进行移位或者反码,快了不少。

无论学习什么东西,基础、原理性质的东西一定要好好学。不要以为用的少了就不重视。

更多位元算的功能:

911博客:http://www.cnblogs.com/911/archive/2008/05/20/1203477.html

csdn/人在江湖:http://blog.csdn.net/zmazon/article/details/8262185

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 20:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表