一、不用额外变量交换两个整数的值
a=a^b; b=a^b; a=a^b;
- 或者：
a=a+b; b=a-b; a=a-b;
二、不用任何比较判断找出两个数中较大的数
有两种方法，方法一有一定的局限性，a-b的值可能溢出，这样溢出后符号改变，返回结果就不正确。
而方法二对a和b是否异号进行了判断，如果同号，则按照方法一返回，否则直接返回正的数就行。
a-b的值如果为0的处理按照大于0处理。
//如果n为1，则返回0；如果n为0，则返回1 public static int flip(int n) { return n ^ 1; } //返回整数n的符号，正数和0返回1，负数返回0 public static int sign(int n) { return flip((n >> 31) & 1); } //方法一 public static int getMax1(int a, int b) { int c = a - b; int scA = sign(c); int scB = flip(scA); return a * scA + b * scB; } //方法二 public static int getMax2(int a, int b) { int c = a - b; int sa = sign(a); int sb = sign(b); int sc = sign(c); int difSab = sa ^ sb; int sameSab = flip(difSab); int returnA = difSab * sa + sameSab * sc; int returnB = flip(returnA); return a * returnA + b * returnB; }
三、整数的二进制表达式中有多少个1
题目：
给定一个32位整数n,可为0、整数、负数。返回该整数二进制表达式中1的个数。
首先简单介绍一下移位操作符：
移位操作符只可用来处理整型类型。左移位操作符(<<)能按照操作符右侧指定的位数将操作符左边的操作数向左移动（在低位补0）。“有符号”右移位操作符(>>)则按照操作符右侧指定的位数将操作符左边的操作数向右移动。“有符号”右移位操作符使用“符号扩展”：若符号为正，则在高位插入0；若符号为负，则在高位插入1。java中增加了一种“无符号”右移位操作符(>>>)，它使用”零扩展”：无论正负，都在高位插入。
解法一：
最简单的解法。
每次进行无符号右移一位，检查最右边的bit是否为1。最复杂的情况下要进行32次循环。
public static int count1(int n) { int res = 0; while (n != 0) { res += n & 1; n >>>= 1; } return res; }
解法二：
循环次数与1的个数有关。每次循环去掉最右侧的1。
public static int count2(int n) { int res = 0; while (n != 0) { n &= (n - 1); res++; } return res; }
解法三：
与解法二大致相同，只是删除最右侧1的方式不同。
public static int count3(int n) { int res = 0; while (n != 0) { n -= n & (~n + 1); res++; } return res; }
解法四：
平行算法：
public static int count4(int n) { n = (n & 0x55555555) + ((n >>> 1) & 0x55555555); n = (n & 0x33333333) + ((n >>> 2) & 0x33333333); n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f); n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff); n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff); return n;
解法五：
MIT hakmem
public int count5(int x) { int temp = x - (x >>> 1) & 033333333333 - (x >>> 2) & 011111111111; return (temp +(temp >>>3)) & 030707070707 % 63; }
HAKMEM (Hacks Memo) is a legendary collection of neat mathematical and programming hacks contributed mostly by people at MIT and some elsewhere. This source is from the MIT AI LABS and this brilliant piece of code orginally in assembly was probably conceived in the late 70’s.
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;
}
Lets take a look at the theory behind this idea.
Take a 32bit number n;n = a31 * 231 + a30 * 230 +.....+ ak * 2k +....+ a1 * 2 + a0;
Here a0 through a31 are the values of bits (0 or 1) in a 32 bit number. Since the problem at hand is to count the number of set bits in the number, simply summing up these co-efficients would yeild the solution. (a0 + a1 +..+ a31 ).
How do we do this programmatically?
Take the original number n and store in the count variable.count=n;
Shift the orignal number 1 bit to the right and subtract from the orignal.count = n - (n >>1);
Now Shift the original number 2 bits to the right and subtract from count;count = n - (n>>1) - (n>>2);
Keep doing this until you reach the end.count = n - (n>>1) - (n>>2) - ... -( n>>31);
Let analyze and see what count holds now.n = a31 * 231 + a30 * 230 +.....+ ak * 2k +....+ a1 * 2 + a0;
n >> 1 = a31 * 230 + a30 * 229 +.....+ ak * 2k-1 +....+ a1;
n >> 2 = a31 * 229 + a30 * 228 +.....+ ak* 2k-2 +....+ a2
;
..
n >> k = a31 * 2(31-k) + a30 * 2(30-k) +…..+ ak * 2k;
..
n>>31 = a31;
You can quickly see that: (Hint: 2k - 2k-1 = 2k-1; )count = n - (n>>1) - (n>>2) - ... -( n>>31) =a31+ a30 +..+a0;
which is what we are looking for;
int BitCount(unsigned int u)
{
unsigned int uCount=u;
do
{
u=u>>1;
uCount -= u;
}
while(u);
}
This certainaly is an interesting way to solve this problem. But how do you make this brilliant? Run this in constant time with constant memory!!.
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;
}
For those of you who are still wondering whats going? Basically use the same idea, but instead of looping over the entire number, sum up the number in blocks of 3 (octal) and count them in parallel.
After this statement uCount = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
uCount has the sum of bits in each octal block spread out through itself.
So if you can a block of 3 bits
u = a222 + a12+ a0;
u>>1 = a2*2 + a1;
u>>2 = a2;
u - (u>>1) - (u>>2) is a2+a1+a0 which is the sum of bits in each block of 3 bits.
The nexe step is to grab all these and sum them up:
((uCount + (uCount >> 3)) will re-arrange them in blocks of 6 bits and sum them up in such a way the every other block of 3 has the sum of number of set bits in the original number plus the preceding block of 3. The only expection here is the first block of 3. The idea is not to spill over the bits to adjacent blocks while summing them up. How is that made possible. Well, the maximum number of set bits in a block of 3 is 3, in a block of 6 is 6. and 3 bits can represent upto 7. This way you make sure you dont spill the bits over. To mask out the junk while doing a uCount>>3. Do and AND with030707070707. THe only expection is the first block as I just mentioned.
What does ((uCount + (uCount >> 3)) & 030707070707) hold now?
Its 2^0 * (2^6 - 1) * sum0 + 2^1 * (2^6 - 1) * sum1 + 2^2 * (2^6 - 1) * sum2 + 2^3 * (2^6 - 1) * sum3 + 2^4 * (2^6 - 1) * sum4 + 2^5 * (2^3 - 1) * sum5
where sum0 is the sum of number of set bits in every block of 6 bits starting from the ‘low’ position.
What we need is sum0 + sum1 + sum2 + sum3 + sum4 + sum5;
2^6-1
解法六：
查表：
public int static4bit(int x) { int[] table = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; int c = 0; for (; x > 0; x >>>= 4) { c += table[x & 0xF]; } return c; } /** * 首先构造一个包含256个元素的表table，table[i]即i中1的个数，这里的i是[0-255]之间任意一个值。 * 然后对于任意一个32bit无符号整数n * ，我们将其拆分成四个8bit，然后分别求出每个8bit中1的个数，再累加求和即可，这里用移位的方法，每次右移8位 * ，并与0xff相与，取得最低位的8bit * ，累加后继续移位，如此往复，直到n为0。所以对于任意一个32位整数，需要查表4次。以十进制数2882400018为例 * ，其对应的二进制数为10101011110011011110111100010010 * ，对应的四次查表过程如下：红色表示当前8bit，绿色表示右移后高位补零。 * * 第一次（n & 0xff） 10101011110011011110111100010010 * * 第二次（(n >> 8) & 0xff） 00000000101010111100110111101111 * * 第三次（(n >> 16) & 0xff）00000000000000001010101111001101 * * 第四次（(n >> 24) & 0xff）00000000000000000000000010101011 */ public int static8bit(int x) { int[] table = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,}; int c = 0; for (; x > 0; x >>>= 8) { c += table[x & 0xFF]; } return c; }