JAVA 位操作学习
一,基础知识
计算机中数值的编码方式中,原码、反码、补码。
正数的补码与原码相同,负数的补码为:负数的原码符号位不变,其它位取反,再加1。
在计算机中,数值是以补码的形式存储的。补码的好处:
①用补码存储可以减化电路设计,因为它可以将减法转换成加法,简化运算规则,将加减法统一起来了。
②还可以不用考虑符号位,解决了0的两种表示方式:比如,在原码中0的表示有 +0 和 -0
+0=[0000 0000 0000 0000 0000 0000 0000 0000]原
-0=[1000 0000 0000 0000 0000 0000 0000 0000]原
而用补码表示时,[0000 0000 0000 0000 0000 0000 0000 0000]补用来表示0,而[1000 0000 0000 0000 0000 0000 0000 0000]补用来表示 -2^32
这也是为什么我们看到JAVA中int型的数值范围为[-2^32 , 2^32-1]的原因。可表示的负数比可表示的正数多了一个。这个多出来的负数就是用原码中的-0 来表示 -128
二,JAVA中int型的最大值、最小值表示
在JAVA中,int型整数是用32个bit来表示的。最高位为符号位。下面都是以32bit的数值进行举例。
因此,JAVA中最大值int型整数为: (1<<31)-1,值为:2^32-1。它在内存中存储的形式为补码形式:[0111 1111 1111 1111 1111 1111 1111 1111]补
JAVA中最小的int型整数可用 1 移位得到: (1<<31),值为:-2^32。它在内存中的形式为补码形式:[1000 0000 0000 0000 0000 0000 0000 0000]补
此外,java.util.BitSet类也可以进行一些与 位 相关的操作。
三,负数的模操作(求余%)
当 x < 0 时,负数的取模操作如下:
x mod y = x - (<x/y>)
x % y = x 减去 (y 乘上 x与y的商的下界).<x/y>表示 x/y 的下界
四,JAVA 位操作的应用
这里演示异或操作的一个简单应用
①任何 int 型整数 与 0 异或 得到该整数本身
②任何 int 型整数 与 自己本身异或 得到 0
举例: 3^4^5^4^5 = 3
因为:3^4^5^4^5 = 4^4^5^5^3=3 (4^4=0,5^5=0,0^3=3)
根据以上两个性质,可以求解这个问题:
给定一个数组,除了一个元素,其它每个元素都出现了两次,找出这个出现一次的元素。时间复杂度O(n), 空间复杂度O(1).(链接)
同样,也可以类似地求解这个问题:
给一个长度为 n-1的数组,数字的范围在 1到 n(无重复),其中有一个缺失的数字,找出该数字。要求时间复杂度为O(n),空间复杂度为O(1).(链接)
思路就是,0 与该数组中的所有元素进行异或,再与 1,2,3,……n 异或。这样,那个缺失的数字在异或操作中只出现一次。异或的最终结果即为那个缺失的数字。
如:3^4^5^4^5 = 4^4^5^5^3 =3(4^4=0,5^5=0,0^3=3)
代码如下:
public class Solution {
public static int singleNumber(int[] nums) {
int ans = 0;
int i = 0;
for(;i < nums.length; i++)
ans = ans ^ nums[i] ^ (i+1);
return (ans^(i+1));
} public static void main(String[] args) {
int[] nums = {3,4,1,5,7,6};
int r = singleNumber(nums);
System.out.println(r);//2
}
}
五,参考资料
关于原码、补码、反码、求余参考
关于JAVA位操作应用参考:Java位操作全面总结
最新文章
- swift学习笔记5——其它部分(自动引用计数、错误处理、泛型...)
- MySQL分表自增ID解决方案(转)
- BZOJ 1059 &; 二分图匹配
- Linux命令之reset - 终端屏幕混乱的终结者
- JavaScript高级 面向对象的程序设计 (二)《JavaScript高级程序设计(第三版)》
- YouTube上的版权保护
- oracle连接由于防火墙设置导致超时的问题
- 我眼中的go的语法特点
- POJ 1160 Post Office (动态规划)
- TypeScript设计模式之单例、建造者、原型
- echarts柱图自定义为硬币堆叠的形式
- 1.熟悉Java基本类库系列 - 目录
- Reading task(Introduction to Algorithms. 2nd)
- 常量(constant)
- CPU温度的实现
- php is_callable()与method_exists()函数
- vuex 开始
- 【UVa】Salesmen(dp)
- tc:逼良为娼
- gitHub优秀android项目
热门文章
- gulp.src()内部实现探究
- 安装loadrunner11出现Microsoft Visual c++2005 sp1安装失败
- CentOS 6.8 安装Tomcat7
- B1048 数字加密
- [T-ARA][결혼 하지마][不要结婚]
- PHP学习 Cookie和Session
- 前后端同学必会的Linux基础命令
- wpf-典型的mvvm模式通用中小型管理系统框架0
- 11慕课网《进击Node.js基础(一)》Buffer和Stream
- think in UML(二)