浅谈程序设计中的位操作什么是位操作位操作的常用技巧位操作的应用,常见的算法题小结

位操作是一种很底层的操作二进制数据的方法,虽然比较难掌握,但是有时候却有更高的效率和难以名状的优雅感。而且,在面试或者笔试中,考察基本的位操作应用越老越普遍,所以掌握位操作的基本操作和应用很有必要。 我们先从基本的位操作概念和基础谈起,并介绍其在程序中的用处比较多的应用,最后根据几道常用的算法题来总结升华。

什么是位操作

我们都知道数据在计算机存储的形式是二进制数据,位操作就是一种在二进制层面操作数据的方法,位操作直接操作0,1构成的二进制数据。

基本的位操作

基本的位操作有六种,分别是 ** 与 或 非 异或 左移 右移 **

符号

描述

运算规则

&

两个位都为1时,结果才为1

两个位都为0时,结果才为0

^

异或

两个位相同时,结果为1,不相同为0

~

取反

0变1,1变0

<<

左移

各二进位全部左移若干位,高位丢弃,低位补0

>>

右移

各二进位全部左移若干位,高位丢弃,高位补符号位,或者补零,根据不同编译器

  • ** 首先,必须明确位操作只能对整数进行操作 **
  • 在jdk中,java右移是进行算术右移操作
  • ** 位操作的优先级很低,所以最好用括号 **
public class Byte {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a = 13, b = -13;
        System.out.println(a>>2);
        System.out.println(b>>2);
    }

}

上述代码的输出结果:

byte.PNG

下面我们就分析一下为什么会输出这个结果:

  • 首先对于13,我们写出他的二进制:0000 1101
  • 右移两位: 0000 0011,由于jdk中的右移是算术右移,所以高位补00,结果为3
  • 对于-13,二进制代码: 1111 0011
  • 右移两位,高位补符号位,1111 1100,结果是-4

位操作的常用技巧

位操作经常用于一些小操作,由于他只能操作整形数,所以用途有限,但是一些常用的小技巧是非常值得掌握的,判断奇偶,交换两数,交换符号,求绝对值等。下面我们就将一一介绍。

判断奇偶

奇偶的区别体现在二进制上,就是末尾是0,1 显然当末尾为0时,是偶数,当末尾为1是最后一位奇数。所以判断奇偶的方法是:

if (a & 1 == 0)
  为偶数
else
  为奇数  

一个小的测试程序:

        for(int i=0;i<1000;i++)
        {
            if((i & 1) == 0)
                System.out.println(i);
        }

上面这个程序将会输出所有1000以内的偶数

交换两数

利用位操作交换两个数的好处是不用第三个temp变量(局限是只能交换整数变量)

        if (a != b)  
        {  
            a ^= b;  
            b ^= a;  
            a ^= b;  
        } 

分析一下交换是怎么产生的: 首先 a^=b 即a=(a^b); b^=a 即b=b(ab),由于运算满足交换律,b(ab)=bb^a。一个数和自己异或肯定是0,因为自己肯定是等于自己的啦,那么一个数和0异或的话,1和0异或还是1,0和0异或还是0,所以显然一个数和0异或之后当然还是自己本身。所以此时,b被赋值为a。 最后一步,a^=b 就是a=ab,由于前面二步可知a=(ab),b=a,所以a=ab即a=(ab)^a。故a会被赋上b的值。

变换符号

变换符号显然很简单,根据类似补码,取反加一就可以了。

int SignReversal(int a)  
{  
    return ~a + 1;  
} 

求绝对值

求绝对值就是在变换符号的基础上实现的,我们只要先判断是否为负数,若是负数,就变换符号,不是,就直接返回。 判断正负可以直接判断其符号位,右移31位,取到符号位,判断正负

int my_abs(int a)  
{  
    int i = a >> 31;  
    return i == 0 ? a : (~a + 1);  
}

对于任何数,与0异或都会保持不变,与-1即0xFFFFFFFF异或就相当于取反。因此,a与i异或后再减i(因为i为0或-1,所以减i即是要么加0要么加1)也可以得到绝对值。所以可以对上面代码优化下:

int my_abs(int a)  
{  
    int i = a >> 31;  
    return ((a ^ i) - i);  
} 

位操作的应用,常见的算法题

位操作实现A+B的操作是常见的算法题。 lintcode上就有一道容易题是这样。

class Solution {
    /*
     * param a: The first integer
     * param b: The second integer
     * return: The sum of a and b
     */
    public int aplusb(int a, int b) {
        // write your code here, try to do it without arithmetic operators.
        if(a==0)return b;  
        if(b==0)return a;  
        int x1 = a^b;  
        int x2 = (a&b)<<1;  
        return aplusb(x1,x2); 
    }
};

上述代码就实现了不用+操作符,利用位操作实现两个数的相加操作。 现在我们来讲解位操作实现两个数相加的原理 首先,十进制中,我们知道,7+8,不进位和是5,进位是1,然后我们可以根据不进位和和进位5+1*10算出最后的结果15。 类似二进制也可以采取这种方法 比如 a = 3,b = 6 a : 0011 b : 0110 不进位和: 0101 也就是5 进位:0010 也就是2 所以a+b变成5 + (2<<1) 5    0101 2<<1   0100 不进位和 0001 = 1 进位 0100 = 4 因此 a + b就变成了1 + 4 << 1 然后有 1    0001 4<<1   1000 不进位和 1001 = 9 进位 0000 = 0 当时进位为0时,不进位和为9即a + b之和。

可以发现上述是一个递归的过程,所以也就不难写出代码了。求两个数的不进位和实际上就是将两个数异或操作即可。

小结

我们先从六种基本的位操作入手,然后介绍了位操作的常用技巧,判断奇偶,求绝对值,交换符号,交换两个数。最后根据常用的算法题中,利用位操作实现两个数相加。基本总结了位操作简单的应用。 位操作当然还有更丰富复杂的应用,需要我们在学习过程中不断总结。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LanceToBigData

MySQL(六)之MySQL常用操作符

前言 在前面的MySQL学习中,我们学习了MySQL的安装,管理以及配置,还有是它的DDL。今天给大家分享一下,MySQL的操作符。 千里之行始于足下,做什么事...

32380
来自专栏深度学习之tensorflow实战篇

hive中数据类型的转化CAST

在《Hive内置数据类型》文章中,我们提到了Hive内置数据类型由基本数据类型和复杂数据类型组成。今天的话题是Hive数据类型之间的转换。同Java语言一样,H...

1.6K30
来自专栏lgp20151222

js遍历 for-of

11220
来自专栏PHP在线

使用MySQL正则表达式 __MySQL必知必会

正则表达式作用是匹配方本,将一个模式(正则表达式)与一个文本串进行比较。 MySQL用WHERE子句对正则表达式提供了初步的支持,允许你指定用正则表达式过滤SE...

39090
来自专栏码匠的流水账

聊聊base62与tinyURL

base64大家肯定是很熟悉了,那base62是什么东东,它常被用来做短url的映射。

17920
来自专栏dotnet & java

用泛型来实现编译时期的类型推断

第一章都是讲泛型的,距离上一篇Effective C#的随笔已经是很久以前的事情了。。。

9330
来自专栏Django Scrapy

Django 数据库|models操作

相关API 1.get(**kwargs) 解释:返回与筛选条件相匹配的Model对象,返回结果有且只有一个。 说明:如果符合条件的对象多于一个抛出Multi...

34570
来自专栏web前端教室

javascript 红皮高程(13)

复习下昨天的一元操作符中的递增和递减操作符,++和-- 只能操作一个值的操作符叫做一元操作符。 它的规则主要在37页, (1)应用于不包括数字的字符串时,将把变...

217100
来自专栏指尖下的Android

Java &、&&、|、||、^、<<、>>、~、>>>等运算符

无符号右移运算符和右移运算符的主要区别在于负数的计算,因为无符号右移是高位补0,移多少位补多少个0。

19.1K40
来自专栏lgp20151222

MySql 模糊查询

SQL模糊查询,使用like比较关键字,加上SQL里的通配符,请参考以下:  1、LIKE'Mc%' 将搜索以字母 Mc 开头的所有字符串(如 McBadden...

11110

扫码关注云+社区

领取腾讯云代金券