参考这个解法
这是大佬的源码；
/**
* 负数在参与位运算时使用的是补码
* -1的原码是 10000000 00000000 00000000 00000001
* -1的反码是 11111111 11111111 11111111 11111110
* -1的补码是 11111111 11111111 11111111 11111111
* 因此任何数与-1做与运算的结果任然为原数
*/
public static int sumNums(int n) {
/**
* 由等差数列求和公式可知，结果等于n*(n+1)/2，其中除以2可以通过右移1位进行操作
* 但n*(n+1)在不允许使用乘法的情况下，只能把n或n+1其中一个拆解为2的n次幂数之和，配合另一个来进行位运算和累加
* 此代码利用了-1和任何整数进行与运算还等于原数的特点
* -(n + 1 >> 0 & 1)用于求从低到高第i+1位如果为0取，如果为1取-1
*/
int n1 = (n & -(n + 1 >> 0 & 1)) << 0;
int n2 = (n & -(n + 1 >> 1 & 1)) << 1;
int n3 = (n & -(n + 1 >> 2 & 1)) << 2;
int n4 = (n & -(n + 1 >> 3 & 1)) << 3;
int n5 = (n & -(n + 1 >> 4 & 1)) << 4;
int n6 = (n & -(n + 1 >> 5 & 1)) << 5;
int n7 = (n & -(n + 1 >> 6 & 1)) << 6;
int n8 = (n & -(n + 1 >> 7 & 1)) << 7;
int n9 = (n & -(n + 1 >> 8 & 1)) << 8;
int n10 = (n & -(n + 1 >> 9 & 1)) << 9;
int n11 = (n & -(n + 1 >> 10 & 1)) << 10;
int n12 = (n & -(n + 1 >> 11 & 1)) << 11;
int n13 = (n & -(n + 1 >> 12 & 1)) << 12;
int n14 = (n & -(n + 1 >> 13 & 1)) << 13;
System.out.println(n1+"--"+n2+"--"+n3+"--"+n4+"--"+n5+"--"+n6+"--"+n7+"--"+n8+"--"+n9
+"--"+n10+"--"+n11+"--"+n12+"--"+n13+"--"+n14);
return (n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8 + n9 + n10 + n11 + n12 + n13 + n14) >> 1;
}
这是自己的分析过程
int n = 48;
//将48分解成0011,0000，并且从小到大依次移动位数，
//00110001与0000,0001作比较==>0000,0001==>0,可知第8个数是1
//00011000与0000,0001作比较==>0000,0001==>0,可知第7个数是0
//00001100与0000,0001作比较==>0000,0001==>0,可知第6个数是0
//00000110与0000,0001作比较==>0000,0001==>0,可知第5个数是0
//00000011与0000,0001作比较==>0000,0001==>1,可知第4个数是1
//00000001与0000,0001作比较==>0000,0001==>1,可知第3个数是1
//00000000与0000,0001作比较==>0000,0001==>0,可知第2个数是0
//00000000与0000,0001作比较==>0000,0001==>0,可知第1个数是0
System.out.println(n + 1 >> 0 & 1);
System.out.println(n + 1 >> 1 & 1);
System.out.println(n + 1 >> 2 & 1);
System.out.println(n + 1 >> 3 & 1);
System.out.println(n + 1 >> 4 & 1);
System.out.println(n + 1 >> 5 & 1);
System.out.println(n + 1 >> 6 & 1);
System.out.println(n + 1 >> 7 & 1);
System.out.println(n + 1 >> 8 & 1);
System.out.println("==============");
//0->-1
//0->0
//0->0
//0->0
//1->-1
//1->-1
//0->0
//0->0
//0->0
//0->0
System.out.println(-(n + 1 >> 0 & 1));
System.out.println(-(n + 1 >> 1 & 1));
System.out.println(-(n + 1 >> 2 & 1));
System.out.println(-(n + 1 >> 3 & 1));
System.out.println(-(n + 1 >> 4 & 1));
System.out.println(-(n + 1 >> 5 & 1));
System.out.println(-(n + 1 >> 6 & 1));
System.out.println(-(n + 1 >> 7 & 1));
System.out.println(-(n + 1 >> 8 & 1));
System.out.println("==============");
System.out.println("-1的二进制：" + Integer.toBinaryString(-1));
//因此任何数与-1做与运算的结果任然为原数
//-1&48==>11111111&00110000==>00000001==>48
//0&48==>00000000&00110000==>00000000==>0
//0&48==>00000000&00110000==>00000000==>0
//0&48==>00000000&00110000==>00000000==>0
//-1&48==>11111111&00110000==>00110000==>48
//-1&48==>11111111&00110000==>00110000==>48
//0&48==>00000000&00110000==>00000000==>0
//0&48==>00000000&00110000==>00000000==>0
System.out.println(n & -(n + 1 >> 0 & 1));
System.out.println(n & -(n + 1 >> 1 & 1));
System.out.println(n & -(n + 1 >> 2 & 1));
System.out.println(n & -(n + 1 >> 3 & 1));
System.out.println(n & -(n + 1 >> 4 & 1));
System.out.println(n & -(n + 1 >> 5 & 1));
System.out.println(n & -(n + 1 >> 6 & 1));
System.out.println(n & -(n + 1 >> 7 & 1));
System.out.println(n & -(n + 1 >> 8 & 1));
System.out.println("=========================");
//按照幂次扩大，不是很理解为什么这一步的操作，就整体而言，如何从将整体分解成这几步的想法搞不懂，难受
//00000001==>48<<0==>000000000001==>48
//00000000==>0 <<2==>000000000000==>0
//00000000==>0 <<3==>000000000000==>0
//00000000==>0 <<4==>000000000000==>0
//00110000==>48<<5==>000110000000==>768
//00110000==>48<<6==>011000000000==>1536
//00000000==>0 <<7==>000000000000==>0
//00000000==>0 <<8==>000000000000==>0
System.out.println((n & -(n + 1 >> 0 & 1)) << 0);
System.out.println((n & -(n + 1 >> 1 & 1)) << 1);
System.out.println((n & -(n + 1 >> 2 & 1)) << 2);
System.out.println((n & -(n + 1 >> 3 & 1)) << 3);
System.out.println((n & -(n + 1 >> 4 & 1)) << 4);
System.out.println((n & -(n + 1 >> 5 & 1)) << 5);
System.out.println((n & -(n + 1 >> 6 & 1)) << 6);
System.out.println((n & -(n + 1 >> 7 & 1)) << 7);
System.out.println((n & -(n + 1 >> 8 & 1)) << 8);
System.out.println();
//结果==>48+768+1536 << 1 == 1176
解法二：
> https://leetcode-cn.com/problems/qiu-12n-lcof/solution/mian-shi-ti-64-qiu-1-2-nluo-ji-fu-duan-lu-qing-xi-/
public int sum(int n){
//还是用递归的形式相加可符合题目，那么剩下的问题就是递归的终止判断条件，既然不能用if，很多解法给的是boolen判断，
//但是，不知道boolen的判断形式是不是也是用if形式做的源码处理
//n + (n-1) + (n-2) + (n-3) ...直到n > 1
boolean x = n > 1 && (n += sum(n - 1)) > 0;
return n;
}
京公网安备 11010502036488号