文档章节

Java位运算经典实例

不最醉不龟归
 不最醉不龟归
发布于 2017/07/16 09:53
字数 768
阅读 24
收藏 1

一 源码、反码、补码

 

正数的源码、反码、补码相同,例如5:

           5的源码:101

           5的反码:101

           5的补码:101

负数的源码、反码、补码不同,例如-5:

           -5的源码:10000101

           -5的反码:111111010 (取反操作)

           -5的补码:111111011 (补码加1操作)

计算机所有数据都以补码存储和运算。

二 位操作

      位操作包含&,|,!分别表示与,或非。

    eg:

               5 & 4 = 101 & 100 = 100(按位取“与”,1 & 1 = 1,0 & 1 = 0)

               5 | 4 = 101 | 100 = 101  (按位取“或”,1 | 0 = 1, 0 | 0 = 0)

                    !5    = ! 101 = 010  (按位取“反”,!1  = 0, !0  = 1)

三 位运算实例

          eg:给定一个有符号整数X(32位),写一个方法,检查这个数是否是4的N次方,N是非负整数。

下面是用Java解答这道题:

public class Test {
    public static void main(String[] args) {
        for(int i = -64; i < 400; i+=1) {
            if(isPowerOfFour5(i))
            System.out.println("test "+ i + " is power of four!");
        }
    }

    public static boolean isPowerOfFour1(int x) {
        if(x == 0) return false;
        while ((x % 4) == 0) {
            x /= 4;
        }
        return x == 1;
    }
   
    public static boolean isPowerOfFour2(int x) {
        if(x == 0) return false;
        while ((x % 4) == 0) {
            x >>= 2;
        }
        return x == 1;
    }
   
    public static boolean isPowerOfFour3(int x) {
         double n = Math.log(x) / Math.log(4);
         if(n -(int)n != 0) return false;
         return n >= 0;
    }
   
    public static boolean isPowerOfFour4(int x) {
        if(x == 0) return false;
       int y = (int) Math.sqrt(x);
        if(y * y == x)
            return ((y & (y-1)) == 0);
        return false;
    }
   
    public static boolean isPowerOfFour5(int x) {
        if(x == 0) return false;
        return (x & (x - 1)) == 0 && (x & 0xAAAAAAAA) == 0;
    }
}

稍微解释一下,第一个方法的算法复杂度是log4X,原理是,凡是4的N次方的数(N是大于等于0的正整数),则对X一直取余,最终结果肯定等于1,比如4 * 4 * 4 = 64。

第二个方法和第一个方法原理一样,>>2相当于/4。

第三个方法利用公式:4N = X  => N = log4X = logX / log4,所以只需要判断N大于等于0且为整数即可(如果n-(int)n != 0表明n不是整数)。

第四个方法的原理如下:

40     41   42    43   …  4n

(22)0 (22)1 (22)2 (22)3 … (22)n

则y = Math.sqrt(x)等于:

20   21    22    23   …  2n

所以我们只需要判断y是整数,且y是2的n次方,n大于等于0且为整数:

判断一个整数y是不是2的n次方,只需要判断y&(y-1)等不等于0即可。

第五种方法的原理如下:

40                        1

41                   100

42              10000

43         1000000

 …

4n     100000000…

可以发现,所有以4为底的N次方的数的2进制都只有1位为1,且为1的这一位在奇数位上。

因此,我们首先判断X的2进制只有一位,且该位不在偶数位上,还要注意0必须除外,因为0&任何数都等于0。

前面说过,x & (x - 1) == 0则表明x是2的n次方,我们应该知道任何2进制只有一位为1的数都可以表示为2的n次方。

既然已经确定x的2进制数只有一位为1,那么(x & 0xAAAAAAAA) == 0表明为1的这一位在奇数位上,因为0xAAAAAAAA = 1010 1010 1010 1010

 

本文转载自:

不最醉不龟归
粉丝 25
博文 443
码字总数 464975
作品 0
深圳
程序员
私信 提问
《Java从小白到大牛精简版》之第6章 运算符(下)

《Java从小白到大牛》纸质版已经上架了!! 本文是《Java从小白到大牛精简版》之第6章 运算符(上)继续... 6.4 位运算符 位运算是以二进位(bit)为单位进行运算的,操作数和结果都是整型数...

tony关东升
2018/06/26
0
0
《Java从小白到大牛精简版》之第6章 运算符(下)

《Java从小白到大牛》纸质版已经隆重上架了!!! 本文是《Java从小白到大牛精简版》之第6章 运算符(上)继续... 6.4 位运算符 位运算是以二进位(bit)为单位进行运算的,操作数和结果都是整型...

tony关东升
2018/06/26
0
0
new一个Object对象占用多少内存?

Java的自动内存管理机制(automatic storage management system known as a garbage collector)省却了很多编码工作,大大地提高了Java的生产力,而且JVM的性能也越来越好,特别是G1的出现,...

杨尚川
2014/03/15
3K
9
2018年java编程语言经典基础知识总结学习

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰
2018/05/21
0
0
优秀程序员不得不知道的20个位运算技巧

一 提起位运算,人们往往想到它的高效性,无论是嵌入式编程还是优化系统的核心代码,适当的运用位运算总是一种迷人的手段,或者当您求职的时候,在代码中写入 适当的位运算也会让您的程序增加...

lizuochao
2012/12/12
56
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
1K
12
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
27
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
23
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
40
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部