初步学习位运算的小总结

文章目录

• 位运算的小总结
• • 位运算是啥
  • 和逻辑运算符的联系与区别
  • 位运算的一些结论和简单应用
  • • 结论①
    • 结论②
    • 结论③
    • 结论④
    • 结论⑤
    • 结论⑥
    • 结论⑦
    • 结论⑧
    • 结论⑨
    • 结论⑩
    • 结论十一
    • 结论十二
    • 结论十三
    • 结论十四
    • 结论十五
    • 结论十六
    • 结论十七
    • 结论十八
  • 总结一下

位运算的小总结

位运算是啥

简单来说位运算其实就是计算机底层对0和1的运算，大概有如下几种：

和逻辑运算符的联系与区别

在二者的区别上看，&&和||只能是逻辑运算符，而&和|可以是逻辑运算符，也可以是位运算符，在表面上看其实逻辑运算符接表达式，而位运算符接数字，这是表面上的区别，先以Java为例，看看逻辑运算符的&&和&，||和|的区别，本质上来说就是可以视为&&是一个会短路的操作，就是一个布尔类型，如果前面是false，那么后面的条件它就不会看了而如果是&，那它会看后面的条件，同样的||和|也是一样的道理，就是我如果前半部分是true的话，那我后半部分就不看了，而|也是一样也看两边，而我们可以用一个代码来看：

import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
out.println("请输入整数 a：");
out.flush();
int a = Integer.parseInt(br.readLine());
out.println("请输入整数 b：");
out.flush();
int b = Integer.parseInt(br.readLine());
out.println("========================");
out.flush();
out.println("1. && 逻辑与 (短路)");
boolean res1 = (b != 0) && (a / b > 1);//就这个表达式而言，如果b为0，则左边为false，它就不会看右边了
// 如果b不为0，则右边才会执行，这时候看a/b是否大于1，如果大于1，则结果为true，否则为false，结果为false
out.println("(b!=0) && (a/b>1) = " + res1);
out.println("左边false → 右边不执行");
out.println("========================");
out.flush();
out.println("2. & 按位与 (不短路)");
try {
boolean res2 = (b != 0) & (a / b > 1);//而这个表达式只有两边都满足才为true，只要有一边不为true，结果就会为false
out.println("结果：" + res2);
} catch (Exception e) {
out.println("报错！因为 & 一定会执行右边，触发除0异常");
}
out.println("========================");
out.flush();
out.println("3. || 逻辑或 (短路)");
boolean res3 = (a > 5) || (a / b > 1);//就这个表达式而言，如果a真的大于5，则右边不会执行，结果为true
// 如果a小于5，则右边才会执行，这时候看a/b是否大于1，如果大于1，则结果为true，否则为false，结果为false
out.println("(a>5) || (a/b>1) = " + res3);
out.println("左边true → 右边不执行");
out.println("========================");
out.flush();
out.println("4. | 按位或 (不短路)");
try {
boolean res4 = (a > 5) | (a / b > 1);//就这个表达式而言，只要有一边为true，结果就会为true，两边都为false，结果为false
out.println("结果：" + res4);
} catch (Exception e) {
out.println("报错！因为 | 一定会执行右边，触发除0异常");
}
br.close();
out.close();
}
}

不过这个逻辑运算符其实和位运算在表面上没有啥关系，但是它们的底层都是二进制来看的，比如说其实和上面的逻辑是相同的，计算机底层的false就是0，true就是1，对于发现了&&前一个条件是0，那后一个条件就不会进系统去判断了，只有左边是 1，才去算右边看是0还是1，而||：左边 为1直接返回 1，右边不执行的，而逻辑运算符的&和|则是不管左边是 0 还是 1，右边一定会全部执行完毕，然后按照纯位运算的规则去计算： & 遵循 “按位与” 规则：两位都是 1，结果才是 1，只要有一个 0，结果就是 0； | 遵循 “按位或” 规则：只要有一个 1，结果就是 1，两位都是 0，结果才是 0。 所以说它和位运算其实有很大的关系，逻辑符|和&计算机底层的true和false其实还是按照位运算得来的。

位运算的一些结论和简单应用

结论①

利用x & 1判断数字x是奇数还是偶数，如果x & 1为0说明是偶数，如果x & 1为1说明是奇数（对负数同样适用，因为负数以补码形式存在计算机中）。

① +3 原码：0000 0011（正数原 = 反 = 补）
② -3 原码：符号位变 1 → 1000 0011
③ -3 反码：符号位不动，数值位全部取反 → 1111 1100
④ -3 补码：反码 + 1 → 1111 1101
运算就和后面的示意图逻辑相同了。

为啥？就是说我们知道x & 1是对数字x进行了只保留 x 的二进制形式的最后一位，其他位全部清零，如果最后一位是1，那肯定是奇数，因为前面原来的二进制位都是2的倍数来的，最后是1，那就在转位十进制的时候会加一个1，就一定是奇数了，同理偶数也一样，举个例子：

10的二进制是1010，和0001进行与运算（同1才为1，有0就是0）：
1 0 1 0
0 0 0 1
↓ ↓ ↓ ↓
0 0 0 0
就说明1010对应的十进制是偶数，和事实相符合
11的二进制是1011，同样和0001进行与运算
1 0 1 1
0 0 0 1
↓ ↓ ↓ ↓
0 0 0 1
就说明1011对应的十进制是奇数，和事实相符合

结论②

x << 1相当于对数字x乘2，x >> 1相当于对数字x除2（向下取整） 同样的，我们示意图来分析：

10的二进制是1010，和0001进行左移运算：
1 0 1 0
← ← ← ←
1 0 1 0 0
整体左挪，右边空出来补0 → 左边顶出一位，位数+1。
而10100对应的十进制为0*1+0*2+1*4+0*8+1*16=20，和结论相符
11的二进制是1011，和0001进行右移运算：
1 0 1 1
→ → → →
0 1 0 1
所有位整体向右挪 1 格，高位空位补 0，低位丢掉最右边 1 位；
而0101对应的十进制是1*1+0*2+1*4+0*8=5（相当于向下取整），和结论相符

有这个结论我们可以拓展出： x << n：整体左移 n 位，右侧补 0 (x × 2^n) x >> n：整体右移 n 位，左侧补 0 (x ÷ 2^n)（向下取整） 而这些结论其实对负数都成立，比如说：

-3的补码是1111 1100
1 1 1 1 1 1 0 1
→ → → → → → → →
1 1 1 1 1 1 1 0
-3的右移符号位 1 不变，左侧空位补 1，结果11111110=-2，同样向下取整

结论③

一个数异或自身为0，异或0为自身，示意图如下：

10的二进制为1010，分别对自身和0进行异或运算（相同为0，不同为1）：
1 0 1 0
1 0 1 0
↓ ↓ ↓ ↓
0 0 0 0
得出结果0，和结论是相符合的
1 0 1 0
0 0 0 0
↓ ↓ ↓ ↓
1 0 1 0
结果得出还是10，和结论相符合

关于这个性质，它有进阶的应用： 进阶一 找数组中唯一出现一次的数，是傻傻的用哈希表来写？那样有点慢，可以进行异或运算，代码如下：

//力扣136题
class Solution {
public int singleNumber(int[] nums) {
int eor = 0;
for(int i=0;i<nums.length;i++){
eor^=nums[i];
}
return eor;
}
}

那么它的原理是啥呢，就是说数组中如果一个元素x出现了偶数次，都和0异或后就是0，而如果奇数次出现最后它会是x^xx…^x0(省略号中有奇数个x)，当前面偶数个x异或运算完了后最后就是x^0=x(它本身） 这样就是这个题为啥可以这样写的原因 进阶二 交换两个数的异或写法，代码如下：

import java.io.*;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
static int a;
static int b;
public static void swap(){
a=a^b;
b=a^b;
a=a^b;
}
public static void main(String[] args)throws IOException{
a=Integer.parseInt(br.readLine());
b=Integer.parseInt(br.readLine());
swap();
out.println(a+" "+b);
out.flush();
br.close();
out.close();
}
}
/*运行结果如下：
输入：
2
3
输出：
3 2
*/

为啥呢？其实还是用到了异或自身为0，异或0为自身的性质：

a=10和b=11的二进制分别为1010和1011，进行上述交换操作
a=1010^1011
1 0 1 0
1 0 1 1
↓ ↓ ↓ ↓
0 0 0 1
得到a=1
b=0001^1011
0 0 0 1
1 0 1 1
↓ ↓ ↓ ↓
1 0 1 0
得到b=10
a=0001^1010
0 0 0 1
1 0 1 0
↓ ↓ ↓ ↓
1 0 1 1
得到a=11
和结论相符合
其实它的原理还是异或的两个性质，就是说第一步a = a^b把 a 存成两数异或的结果；第二步利用x^x=0、x^0=x，b=(a^b)^b = a^(b^b)=a^0，b 就拿到原来 a 的值；第三步再用相同性质，a=(a^b)^a = b^(a^a)=b^0，a 就拿到原来 b 的值，依靠两条固有性质三步就可以完成数值交换。

结论④

取一个数字的二进制最低位的 1可以x & -x 举个例子：

11的二进制是00001011，对它进形结论中的操作：
+11原码：00001011
-11原码：10001011
-11反码：11110100
-11补码：11110101
0 0 0 0 1 0 1 1
1 1 1 1 0 1 0 1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 0 0 0 0 0 0 1
可知11的二进制最低位的1恰好是原数最低位的1
其实就是负数用补码（按位取反 + 1），使x与-x仅在最低位 1 处同为 1，按位与便只取出该位权值，得到它二进制最低位1的位置

这个结论可以应用在树状数组算法中，大概代码如下：

//树状数组（支持：单点修改 + 区间查询）
import java.util.*;
import java.io.*;
public class Main {
// 数组最大长度
static int N = 100010;
// 树状数组本体（下标从 1 开始）
static int[] tree = new int[N];
// 作用：取出 x 二进制最低位的 1，用于树状数组跳转
static int lowbit(int x) {
return x & (–x);
}
// 进行单点更新
// 把下标 x 的位置 加上 v
static void update(int x, int v) {
// 沿着父节点一路向上更新，直到越界
while (x < N) {
tree[x] += v; // 更新当前节点
x += lowbit(x); // lowbit 跳父节点
}
}
//查询前缀和：1~x 的和
static int query(int x) {
int res = 0;
// 沿着子节点一路向下累加
while (x > 0) {
res += tree[x]; // 累加当前区间
x -= lowbit(x); // lowbit 跳子区间
}
return res;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine().trim());
//输入 n 个数字，初始化树状数组
st = new StringTokenizer(br.readLine().trim());
for (int i = 1; i <= n; i++) {
int a = Integer.parseInt(st.nextToken());
update(i, a); // 把第 i 位设为 a（等价于初始化）
}
//输入查询次数 q
int q = Integer.parseInt(br.readLine().trim());
while (q— > 0) {
st = new StringTokenizer(br.readLine().trim());
int op = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
if (op == 1) {
// op=1：查询区间 [l, r] 的和
out.println(query(r) – query(l – 1));
} else {
// op=2：单点修改，把 l 位置 加上 r
update(l, r);
}
}
out.flush();
out.close();
br.close();
}
}

结论⑤

判断一个数是否为 2 的幂，可以用位运算来看且有多种写法，代码如下：

//力扣231题
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
public static boolean isPowerOfTwo(int n) {
return n > 0 && (n & –n) == n;
}
public static boolean isPowerOfTwo1(int n) {
return n > 0 && (n & (n – 1)) == 0;
}
public static boolean isPowerOfTwo2(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}
public static void main(String[] args) throws IOException {
int t = Integer.parseInt(br.readLine().trim());
while (t— > 0) {
int n = Integer.parseInt(br.readLine().trim());
out.println("测试数字：" + n);
out.println("方法1(x&-x) ：" + (isPowerOfTwo(n) ? "YES" : "NO"));
out.println("方法2(n&n-1)：" + (isPowerOfTwo1(n) ? "YES" : "NO"));
out.println("方法3(bitCount)：" + (isPowerOfTwo2(n) ? "YES" : "NO"));
out.println("————————");
}
out.flush();
br.close();
out.close();
}
}
/*
运行结果如下：
2
8
6
测试数字：8
方法1(x&-x) ：YES
方法2(n&n-1)：YES
方法3(bitCount)：YES
————————
测试数字：6
方法1(x&-x) ：NO
方法2(n&n-1)：NO
方法3(bitCount)：NO
————————

进程已结束，退出代码为 0
*/

把它们单独拿出来看：

public static boolean isPowerOfTwo(int n) {
return n > 0 && (n & –n) == n;
}
/*
我们以10的二进制1010为例：
有结论④可知（n&-n)取它最低位1出现的位置
对10来看，它的最低位1的位置就是2，所以很明显，2不等于10，10就不是2的幂
再以16为例，它的二进制是10000，（16&-16）=16等于原数，所以16是2的幂
那它的原理是啥呢？
其实就是2 的幂二进制只有 1 个 1，所以 n & -n 会等于它自己；
不是 2 的幂有多个 1，n & -n 只会取出最低位 1，一定小于自己。
*/

public static boolean isPowerOfTwo1(int n) {
return n > 0 && (n & (n – 1)) == 0;
}
/*
还是以10（1010）和16（1000）为例
对10来说：
n = 10 → 1 0 1 0
n-1 = 9 → 1 0 0 1
它们进行与运算就是：
1 0 1 0
1 0 0 1
↓ ↓ ↓ ↓
1 0 0 0
结果为8不为0，即10不是2的幂，和事实相符合
对于16来说：
n = 16 → 1 0 0 0 0
n-1 = 15 → 0 1 1 1 1
它们进行与运算就是：
1 0 0 0 0
0 1 1 1 1
↓ ↓ ↓ ↓ ↓
0 0 0 0 0
结果为0，即16是2的幂，和事实也相符合
它的原理和前一个其实是类似的，就是说如果一个数 n 是 2 的幂：
那它的二进制只有 1 个 1，n-1 会把这个 1 变 0，后面全变 1，按位与必然 = 0
*/

public static boolean isPowerOfTwo2(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}
/*
这个其实还是和前面的结论是一样的：
它的原理是：
Integer.bitCount(n)
作用：统计 n 的二进制里面，有多少个 1
而 2 的幂的定义：
二进制里，有且只有 1 个 1
所以：
bitCount 结果 = 1 → 是2的幂
bitCount 结果 ≠ 1 → 不是2的幂
*/

总的来说，这三种判断其实都是用了二进制的一个性质： 就是在二进制中2的幂有且只有1个1，在此性质下进行的进一步判断，不过为啥三个判断都要加上数字大于0的前提？其实就是想想也知道，2的幂不可能是负数，如果一个数是负数了，那它就不可能是2的幂了。

结论⑥

判断一个数是不是3的幂，其实就是如果一个数字是3的某次幂，那么这个数一定只含有3这个质数因子，而1162261467是int型范围内，最大的3的幂，它是3的19次方，这个1162261467只含有3这个质数因子，如果n也是只含有3这个质数因子，那么1162261467 % n == 0，反之如果1162261467 % n != 0 说明n一定含有其他因子，它就不是3的幂，代码如下：

//力扣326题
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}

结论⑦

判断一个数是不是4的幂，其实我们知道，一个数如果是4的幂，那它一定也是2的幂，而且4 的幂二进制的 1 只能出现在 0、2、4、6… 偶数位，比如说16（二进制为10000，1出现的位置为4），而0x55555555 是二进制：01010101010101010101010101010101 这个数的特点为只有偶数位是 1，我们将我们要判断的数字和他进行与运算，那么如果结果不为 0，就说明这个数的 1 恰好落在了偶数位上，满足 4 的幂的要求；如果结果为 0，就说明 1 在奇数位，只是 2 的幂但不是 4 的幂。这样我们就可以进行判断了，代码如下：

//力扣342题
class Solution {
public boolean isPowerOfFour(int n) {
//首先他先要是2的幂
return n > 0&&(n & (n – 1)) == 0&&(n & 0x55555555)!= 0;
}
}

结论⑧

输出一个数字的二进制中1的个数，先看代码：

//力扣191题
class Solution {
public int hammingWeight(int n) {
int cnt = 0;
while (n != 0) {
n = n & (n – 1);
cnt++;
}
return cnt;
}
}
/*
本质上来说，我们利用位运算来看一个数的二进制中1的个数：
那我们可以这样看，我便利它的二进制，把二进制里的1全变为0，每次让计数器加加，就可得到其中一的个数。
就是说我n=n&(n-1)就是一个消1为0的操作，比如10，它的二进制是1010，我们对它进行上述操作：
1 0 1 0
1 0 0 1
↓ ↓ ↓ ↓
1 0 0 0
一次就消去一个1了，第二次：
1 0 0 0
0 1 1 1
↓ ↓ ↓ ↓
0 0 0 0
就把它变为0了，我们的计数器自增了为2，就说明10的二进制里有2个1.
*/

结论⑨

求两个数字对应二进制位不同的位置的数目，还是先看代码：

//力扣461题
class Solution {
public int hammingDistance(int x, int y) {
int n=x^y;
int cnt = 0;
while (n != 0) {
n = n & (n – 1);
cnt++;
}
return cnt;
}
}
/*
其实在这里我们要两个数字的二进制的不同数字的个数，能想到啥？
其实是异或，因为异或相同为0，不同为1，我们可以对此进行标记，再对两个数异或后，其实就发现它不同的数字都被前面的异或运算变为了1，此时要看不同的数字个数，就是数异或后的二进制数字中的1的个数，那其实就是结论⑧了。
*/

结论⑩

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数，还是先看代码：

//力扣268题
class Solution {
public int missingNumber(int[] nums) {
int res=0;
int n=nums.length;
for(int i=0;i<=n;i++){
res^=i;
}
for(int num:nums){
res^=num;
}
return res;
}
}
/*
其实这个题还是在找不同，一样的我们能想到异或，其实这里我们知道一个数异或自身为0，一个数异或0得到本身。
那么我们找缺失的数字其就是我们先用一个res来异或1~n，然后来异或数组里的数字，如果说前面异或1~n中数组中有那就相当于异或自身，得到0，最后我们都是成双成对得异或变为0了，留下一个单落下了的数字和前面的0异或得到本身，那就是这个缺失的数字了。
*/

结论十一

颠倒给定的 32 位有符号整数的二进制位，如何搞呢？先看代码：

//力扣190题
public class Solution {
public int reverseBits(int n) {
int res = 0;
for(int i = 0; i < 32; i++){
res <<= 1;
res += n & 1;
n >>>= 1;
}
return res;
}
}
/*
这个怎么想呢？就是这个题要我们反转的是它的二进制位的顺序，就是说 10（二进制是 1010，反转后变为 0101）。
那我们就从原数字的最右边一位一位地把数位取出来，然后依次放到结果数字的最左边，循环 32 次把所有位都处理完，最后就可以得到我们要的反转结果。
而从右边取的操作是n&1,将取到的数字左移则是res<<=1,n >>> 1则是删掉末尾已取的位，这样就可以实现了。
*/

以10的二进制1010为例，操作过程如下：

结论十二

判断两个数是否符号相同，用(a ^ b) 来判断：结果 >=0 符号相同，<0 符号相反，示意图如下：

11和-10进行异或运算
0 0 0 0 1 0 1 1 （11）
1 1 1 1 0 1 1 0 （-10）
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1 1 1 1 1 1 0 1
左边的的一个数位为1，说明负数，和事实相符合
本质上我们看一个二进制数字是否为负数，那就看最高位，如果最高位为1即为负数，为0即是正数
而异或是相同为0，不同为1，那如果我两个数的最高位相同（符号相同），那异或了后就会变为0，得到一个新数为正数，反之则为负数。

结论十三

求两个数字的平均数可以mid = (x & y) + ((x ^ y) >> 1)，先看代码：

import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
while(n— > 0){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b= Integer.parseInt(st.nextToken());
out.println((a & b) + ((a ^ b) >> 1));
}
out.flush();
br.close();
out.close();
}
}
/*
运行结果如下：
2
2 4
5 7
3
6

进程已结束，退出代码为 0
事实上这样求平均数可以做到（a+b)/2的效果，还可以防止溢出
他的原理就是说：平均值 = 进位部分 + 无进位和 / 2
举个例子，还是10(1010)和11（1011）为例：
先进行与运算：
1 0 1 0
1 0 1 1
↓ ↓ ↓ ↓
1 0 1 0
再进行异或运算：
1 0 1 0
1 0 1 1
↓ ↓ ↓ ↓
0 0 0 1
0001 >> 1 = 0000 (0)然后再加上1010（10）得到结果为10，机和事实相符合
不过为啥他能够防止溢出呢？就是说同为很大的数比如a,b都是接近Integer.MAX_VALUE的数字，它们相加就会爆int，就要用long或者更大的数据类型来存了，那我们用位运算，就不会有这种情况，经过了位运算后，数字不会变大，因此可以更安全。
*/

结论十四

判断一个数字的二进制的第k数位是否是1，用(x >> (k-1)) & 1 结果 = 1 表示该位为 1，为0则表示该位为 0，示意图如下：

还是以10（1010）为例：
我们要看它第二位和第三为是否为1，操作过程如下：
先看第二位：
1 0 1 0 右移1位得到 0 1 0 1即为5，再和0 0 0 1进行与运算：
0 1 0 1
0 0 0 1
↓ ↓ ↓ ↓
0 0 0 1
结果为1，即表示第二位为1，与事实相符合
再看第三位：
1 0 1 0 右移2位得到 0 0 1 0即为2，再和0 0 0 1进行与运算：
0 0 1 0
0 0 0 1
↓ ↓ ↓ ↓
0 0 0 0
结果为0，即表示第三位为0，和事实相符合
其实这样的一个操作就是在把第 k 位移到最右边，再 & 1 就能单独把它取出来看

结论十五

将一个数字的二进制的第k位翻转即0变为1，1变为0，用x ^= (1 << (k-1))，示意图如下：

还是以10（1010）为例:
把第三位翻转：
先右移2位，得到0 1 0 0，在和原数进行异或：
1 0 1 0
0 1 0 0
↓ ↓ ↓ ↓
1 1 1 0
成功将第三位翻转过来了

那如果是多位翻转，即把数字二进制的有效位进行翻转，代码如下：

//力扣476题
class Solution {
public int findComplement(int num) {
int cnt = 0;
int temp = num;
while(temp>0){//通过不断地除2来看它二进制的数位
cnt++;
temp >>=1;
}
for(int i=0;i<cnt;i++){//因为下标从0开始的所以就是1<<i了
num ^= (1<<i);
}
return num;
}
}

结论十六

对一个字母字符异或32可以实现大小写转换，即(char)(c^32)=C，代码如下：

import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String s=br.readLine().trim();
StringBuilder sb=new StringBuilder();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(ch>='a'&&ch<='z'){
sb.append((char)(ch^32));
}else if(ch>='A'&&ch<='Z'){
sb.append((char)(ch^32));
}else{
sb.append(ch);
}
}
out.println(sb.toString());
out.flush();
br.close();
out.close();
}
}
/*
运行结果如下：
输入：
1a2B3c4E5f6G
输出：
1A2b3C4e5F6g
那么它的原理是啥呢？其实就是ASCII码表：
在 ASCII 里，同一个字母的大写和小写，二进制只有一位不同的，而数字 32 的二进制是 100000，正好就是第 6 位为 1
所以说：对一个字母字符异或 32，就等于只翻转它的第 6 位，即是：
第 6 位 0 → 1 → 大写变小写
第 6 位 1 → 0 → 小写变大写
*/

结论十七

字母字符大写转小写可以c | 32（或0x20），小写转大写可以c & 223（或0xDF），代码如下：

import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String s=br.readLine().trim();
StringBuilder sb=new StringBuilder();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(ch>='a'&&ch<='z'){
sb.append((char)(ch&223));
}else if(ch>='A'&&ch<='Z'){
sb.append((char)(ch|32));
}else{
sb.append(ch);
}
}
out.println(sb.toString());
out.flush();
br.close();
out.close();
}
}
/*
运行结果如下：
输入：
1a2B3c4E5f
输出：
1A2b3C4e5F
事实上这里还是ASCII码表的应用：
以大写的'A'为例（进行或运算，有1则1，全0则0）：
0 1 0 0 0 0 0 1 (65)
0 0 1 0 0 0 0 0 (32)
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 1 1 0 0 0 0 1 (97) —>即为小写的'a'.
以小写的'a'为例（进行与运算，同1才1，有0则0）：
0 1 1 0 0 0 0 1 （97）
1 1 0 1 1 1 1 1 (223 / 0xDF)
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 1 0 0 0 0 0 1 (65) —>即大写的'A'
其实还是那句话：同一个字母的大写和小写，二进制只有一位不同的。
| 32 = 强制把第 6 位变成 1，& 223 = 强制把第 6 位变成 0
且一个英文字母是大写还是小写，完全由它二进制的第 6 位（从 0 开始数第 5 位）决定的，'A'和'a'在二进制上只有第6位不同，'A'第6位0，'a'第6位为1.

结论十八

位运算的综合使用，写出一套加减乘除及其他运算，代码如下：

import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
// 位运算实现加法
public static long add(long a, long b) {
while (b != 0) {
long sum = a ^ b;
long carry = (a & b) << 1;
a = sum;
b = carry;
}
return a;
}
// 位运算实现减法
public static long sub(long a, long b) {
b = add(~b, 1);
return add(a, b);
}
// 位运算实现乘法
public static long mul(long a, long b) {
boolean negative = (a < 0) ^ (b < 0);
a = a < 0 ? add(~a, 1) : a;
b = b < 0 ? add(~b, 1) : b;
long res = 0;
while (b > 0) {
if ((b & 1) == 1) {
res = add(res, a);
}
a <<= 1;
b >>= 1;
}
return negative ? add(~res, 1) : res;
}
// 位运算实现除法
public static long div(long a, long b) {
if (b == 0) return 0;
boolean negative = (a < 0) ^ (b < 0);
a = a < 0 ? add(~a, 1) : a;
b = b < 0 ? add(~b, 1) : b;
if (a < b) return negative ? –1 : 0;
long res = 0;
for (int i = 62; i >= 0; i—) {
if ((a >> i) >= b) {
res |= (1L << i);
a = sub(a, b << i);
}
}
return negative ? add(~res, 1) : res;
}
// 位运算实现取模
public static long mod(long a, long b) {
if (b == 0) return 0;
long q = div(a, b);
return sub(a, mul(q, b));
}
// 位运算实现阶乘
public static long factorial(int n) {
if (n < 0 || n > 20) {
return –1; // 超过范围返回-1
}
long res = 1;
for (int i = 2; i <= n; i++) {
res = mul(res, i);
}
return res;
}
// 位运算实现幂运算
public static long pow(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) {
res = mul(res, a);
}
a = mul(a, a);
b >>= 1;
}
return res;
}
// 位运算实现整数平方根
public static long sqrt(long x) {
if (x < 0) return –1;
if (x == 0 || x == 1) return x;
long l = 1, r = x, ans = 0;
while (l <= r) {
long mid = div(add(l, r), 2);
long mid2 = mul(mid, mid);
if (mid2 == x) return mid;
if (mid2 < x) {
ans = mid;
l = add(mid, 1);
} else {
r = sub(mid, 1);
}
}
return ans;
}
// 位运算实现向下取整
public static long floorDiv(long a, long b) {
return div(a, b);
}
// 位运算实现向上取整
public static long ceilDiv(long a, long b) {
if (b == 0) return 0;
long temp = add(a, sub(b, 1));
return div(temp, b);
}
// 位运算实现四舍五入
public static long roundDiv(long a, long b) {
if (b == 0) return 0;
long half = div(b, 2);
long temp = add(a, half);
return div(temp, b);
}
public static void main(String[] args) throws IOException {
while (true) {
out.println("============ 纯位运算计算器===========");
out.println("1. 加法 a + b");
out.println("2. 减法 a – b");
out.println("3. 乘法 a * b");
out.println("4. 整除 a / b");
out.println("5. 取模 a % b");
out.println("6. 阶乘 n!");
out.println("7. 幂运算 a^b");
out.println("8. 整数平方根 sqrt(x)");
out.println("9. 向下取整 floor(a/b)");
out.println("10.向上取整 ceil(a/b)");
out.println("11.四舍五入 round(a/b)");
out.println("0. 退出");
out.print("请输入操作：");
out.flush();
int op = Integer.parseInt(br.readLine().trim());
long a, b, res;
if (op == 0) {
out.println("退出成功");
out.flush();
break;
}
switch (op) {
case 1:
out.print("请输入第一个数 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入第二个数 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println(a + " + " + b + " = " + add(a, b));
out.flush();
break;
case 2:
out.print("请输入被减数 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入减数 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println(a + " – " + b + " = " + sub(a, b));
out.flush();
break;
case 3:
out.print("请输入第一个数 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入第二个数 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println(a + " * " + b + " = " + mul(a, b));
out.flush();
break;
case 4:
out.print("请输入被除数 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入除数 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println(a + " / " + b + " = " + div(a, b));
out.flush();
break;
case 5:
out.print("请输入被除数 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入模数 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println(a + " % " + b + " = " + mod(a, b));
out.flush();
break;
case 6:
out.print("请输入 n：");
out.flush();
int n = Integer.parseInt(br.readLine().trim());
long f = factorial(n);
if (f == –1) out.println("错误：n必须在0~20之间");
else out.println(n + "! = " + f);
out.flush();
break;
case 7:
out.print("请输入底数 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入指数 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println(a + "^" + b + " = " + pow(a, b));
out.flush();
break;
case 8:
out.print("请输入 x：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.println("sqrt(" + a + ") = " + sqrt(a));
out.flush();
break;
case 9:
out.print("请输入 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println("floor("+a+"/"+b+") = "+floorDiv(a,b));
out.flush();
break;
case 10:
out.print("请输入 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println("ceil("+a+"/"+b+") = "+ceilDiv(a,b));
out.flush();
break;
case 11:
out.print("请输入 a：");
out.flush();
a = Long.parseLong(br.readLine().trim());
out.print("请输入 b：");
out.flush();
b = Long.parseLong(br.readLine().trim());
out.println("round("+a+"/"+b+") = "+roundDiv(a,b));
out.flush();
break;
default:
out.println("无效输入");
out.flush();
}
out.flush();
}
br.close();
out.close();
}
}
/*
运行结果如下：
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：1
请输入第一个数 a：1
请输入第二个数 b：6
1 + 6 = 7
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：4
请输入被除数 a：7
请输入除数 b：3
7 / 3 = 2
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：2
请输入被减数 a：3
请输入减数 b：5
3 – 5 = -2
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：3
请输入第一个数 a：4
请输入第二个数 b：8
4 * 8 = 32
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：5
请输入被除数 a：6
请输入模数 b：7
6 % 7 = 6
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：6
请输入 n：6
6! = 720
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：8
请输入 x：7
sqrt(7) = 2
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：9
请输入 a：8
请输入 b：6
floor(8/6) = 1
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：10
请输入 a：7
请输入 b：4
ceil(7/4) = 2
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：11
请输入 a：9
请输入 b：6
round(9/6) = 2
============ 纯位运算计算器===========
1. 加法 a + b
2. 减法 a – b
3. 乘法 a * b
4. 整除 a / b
5. 取模 a % b
6. 阶乘 n!
7. 幂运算 a^b
8. 整数平方根 sqrt(x)
9. 向下取整 floor(a/b)
10.向上取整 ceil(a/b)
11.四舍五入 round(a/b)
0. 退出
请输入操作：0
退出成功

进程已结束，退出代码为 0

对于这个代码，需要一个一个来分析： 实际上，以下加减乘除和幂运算就是以上代码的核心，其他的都可以调用这些方法来实现的。 位运算实现加法：

// 位运算实现加法
public static long add(long a, long b) {
// 只要还有进位就一直循环算
while (b != 0) {
// a^b：算出不带进位的本位和，1+1本位变0，进位单独拎出来
long sum = a ^ b;
// a&b：找出全1的位置，这些位要进位；<<1 进位往左挪一位到高位
long carry = (a & b) << 1;
// 本位和存到a，进位存到b，下一轮继续把本位和+进位相加
a = sum;
b = carry;
}
// 进位b变成0，没有进位了，a就是最终相加结果
return a;
}

位运算实现减法：

// 位运算实现减法
public static long sub(long a, long b) {
// 先求 b 的相反数：~b 按位取反，再加 1（补码规则）
b = add(~b, 1);
// a – b 等价于 a + (-b)，调用加法完成计算
return add(a, b);
}

位运算实现乘法：

// 位运算实现乘法
public static long mul(long a, long b) {
// 判断结果正负：一正一负结果为负，同号为正
boolean negative = (a < 0) ^ (b < 0);
// 把 a 变成正数（负数取反+1转绝对值）
a = a < 0 ? add(~a, 1) : a;
// 把 b 变成正数（负数取反+1转绝对值）
b = b < 0 ? add(~b, 1) : b;
// 结果初始化为 0
long res = 0;
// 循环处理 b 的每一位
while (b > 0) {
// 如果 b 当前最低位是 1，就把 a 加到结果里
if ((b & 1) == 1) {
res = add(res, a);
}
// a 左移一位，等价于乘以 2
a <<= 1;
// b 右移一位，处理下一位
b >>= 1;
}
// 如果结果应该是负数，就取反+1变负，否则直接返回
return negative ? add(~res, 1) : res;
}

位运算实现除法：

// 位运算实现除法
public static long div(long a, long b) {
// 除数为0直接返回0
if (b == 0) return 0;
// 判断结果正负：一正一负为负，同号为正
boolean negative = (a < 0) ^ (b < 0);
// 把a转成正数（负数取反+1取绝对值）
a = a < 0 ? add(~a, 1) : a;
// 把b转成正数（负数取反+1取绝对值）
b = b < 0 ? add(~b, 1) : b;
// 被除数小于除数，商为0，负数情况特殊处理
if (a < b) return negative ? –1 : 0;
// 存储最终结果
long res = 0;
// 从高位到低位依次试商
for (int i = 62; i >= 0; i—) {
// 如果 a 右移 i 位后 >= 除数，说明这一位可以商1
if ((a >> i) >= b) {
res |= (1L << i);
// 减去对应的值，继续算剩下的部分
a = sub(a, b << i);
}
}
// 结果需要为负就取反+1，否则直接返回
return negative ? add(~res, 1) : res;
}

位运算实现幂运算：

// 位运算实现幂运算
public static long pow(long a, long b) {
// 结果初始化为 1
long res = 1;
// 快速幂循环，处理指数 b 的每一位
while (b > 0) {
// 如果指数当前最低位是 1，结果就乘上当前的底数
if ((b & 1) == 1) {
res = mul(res, a);
}
// 底数平方，对应指数的高位
a = mul(a, a);
// 指数右移一位，处理下一位
b >>= 1;
}
// 返回最终幂运算结果
return res;
}

特别说明：平方根的手写实现—二分法的应用

// 位运算实现整数平方根
public static long sqrt(long x) {
// 负数不能开平方，直接返回-1
if (x < 0) return –1;
// 0和1的平方根就是自己，直接返回
if (x == 0 || x == 1) return x;
// 二分左右边界，ans保存最终答案
long l = 1, r = x, ans = 0;
while (l <= r) {
// 求中间值mid：(l+r)/2
long mid = div(add(l, r), 2);
// 计算mid的平方
long mid2 = mul(mid, mid);
// 正好等于x，mid就是平方根
if (mid2 == x) return mid;
// mid平方 < x，说明答案可能在右边
if (mid2 < x) {
ans = mid;
l = add(mid, 1);
} else {
// mid平方 > x，答案在左边
r = sub(mid, 1);
}
}
// 返回最后找到的整数平方根（向下取整）
return ans;
}

总结一下

实际上我在学习位运算的过程中，其实也遇到了很多的困难，其实整个位运算都离不开二进制，它们的一些性质都是基于二进制展开的，所以深入计算机底层，提高对源码的关注度，就是我还要进一步加深的地方，加油！