口撕算法
给你一个数,每次可以进行加或减2的n次方操作,最少多少次操作把该数变为0?(将整数减少到零最少操作数)(百度)page 1
对这个数,如果是偶数,直接右移,如果是奇数,将他对4取余,看选择将这个数加一还是减一,当余数时1或3时减一,否则加一,然后增加计数,并把这个数右移。时间复杂度log n。
public static int minOperations(int x) {
int cnt = 0;
// 处理 x 直到等于 0
while (x != 0) {
if ((x & 1) == 0) {
// 偶数,直接右移
x >>= 1;
} else {
// 奇数,决定是 +1 还是 -1
int r = x & 3; // x mod 4
// 当 r==1 或 x==3 时,减 1;否则加 1
if (r == 1 || r == 3 && x == 3) {
x -= 1;
} else {
x += 1;
}
cnt++;
// 处理完最低位后右移
x >>= 1;
}
}
return cnt;
}
有一个数是奇数个,其他都是偶数个,如何找出来奇数的数字(百度)
用异或运算,相同数字异或结果是0,任何数字和0异或是本身,把数组所有数字进行异或,结果就是出现奇数次的数字。