Add 1 to a given number | GeeksforGeeks
Write a program to add one to a given number. You are not allowed to use operators like ‘+’, ‘-’, ‘*’, ‘/’, ‘++’, ‘–’ …etc.
Method 1
To add 1 to a number x (say 0011000111), we need to flip all the bits after the rightmost 0 bit (we get 0011000000). Finally, flip the rightmost 0 bit also (we get 0011001000) and we are done.
int decrement(int x)
{
return (~(-x));
}
Given an integer, add its binary number by 1 without “+” 整数加一, 不用加号.
Write a program to add one to a given number. You are not allowed to use operators like ‘+’, ‘-’, ‘*’, ‘/’, ‘++’, ‘–’ …etc.
Method 1
To add 1 to a number x (say 0011000111), we need to flip all the bits after the rightmost 0 bit (we get 0011000000). Finally, flip the rightmost 0 bit also (we get 0011001000) and we are done.
int
addOne(
int
x)
{
int
m = 1;
/* Flip all the set bits until we find a 0 */
while
( x & m )
{
x = x^m;
m <<= 1;
}
/* flip the rightmost 0 bit */
x = x^m;
return
x;
}
Method 2
We know that the negative number is represented in 2′s complement form on most of the architectures. We have the following lemma hold for 2′s complement representation of signed numbers.
We know that the negative number is represented in 2′s complement form on most of the architectures. We have the following lemma hold for 2′s complement representation of signed numbers.
~x = -(x+1) [ ~ is for bitwise complement ]
To get (x + 1) apply negation once again. So, the final expression becomes (-(~x)).
int addOne( int x) { return (-(~x)); } |
{
return (~(-x));
}
Given an integer, add its binary number by 1 without “+” 整数加一, 不用加号.
public int add(int n) {
for(int i = 0; i < 32; i++) {
if (((1 << i) & n) == 0){ //until we find the first 1 bit
n = n | (1 << i);
break;
}
else
n = n & ~(1 << i); // clean bits
}
return n;
}
- i是游标, (1 << i) 就是对n的每个位从右往左扫.
- if判断的是, 如果这位是 0, 那么就变成1.
- 如果不是, 那么这位肯定是1, 那么在未来的某次循环需要把0 变成1时, 这位肯定要变成0, 所以如果是1 就是0.
- 这里用的是clean bits的方法. 先去取反做mask, 再取与(and).