Interview Question
Country: United States
yeah, it works... there is little typo I think.... nearest power of 2 greater than the number itself.
If given number is 9, then one's complement in 8-Bit Integer machine would be 246.
As per your algorithm, it will return 6 which is incorrect.
Implemented Alex's algorithm. Code works. Thanks.
#include<iostream>
#include<math.h>
using namespace std;
//one's complement
bool check_power_2(int n)
{
if( (n & (n-1))== 0)
return true;
else
return false;
}
int next_power(int n)
{
int c =0;
while(n>0)
{
n = n >> 1;
c++;
}
return pow(2,c);
}
int main()
{
int n;
cin >> n;
if (n == 0)
cout << 1 <<endl;
else if(check_power_2(n))
cout << n-1 << endl;
else
cout << next_power(n) - (n+1) << endl;
return 0;
}
why not simply use bit wise negation operator (~) and also I think that result of right shifting 1 by 31 will be 0 which when XOR with x is going to give x
/*
Code according to Alex's solution.
If the number,n, is an exact power of two, return n-1
else find the nearest power of 2 to the number, find their difference,d, and return d-1
also, if n=0 return 1
ex: n=14
nearest power=16
d=16-14=2
return d-1=1
if n=16, since it is an exact power of 2, return 16-1=15
- alex on January 31, 2013
#include <math.h>
int c153148581sCompliment(int num){
int closestExp2 = ceil(log10((double)num)/log10((double)2));
int closestPower2 = pow(2,closestExp2);
if(num==closestPower2)
return num-1;
else
return closestPower2-num-1;
}
Why is everyone trying to write a program for it when you can use the complement operator (~) like Deepak pointed out?
#include <stdio.h>
int main()
{
int num;
scanf("%d",&num);
if((num & 0x000F) == num)
{
num = num ^ 0x000F;
printf("The 1s complement is %d\n",num);
}
else if((num&0x00FF) == num)
{
num = num ^ 0x00FF;
printf("The 1s complement is %d\n",num);
}
else if((num&0x0FFF) == num)
{
num = num ^ 0x0FFF;
printf("The 1s complement is %d\n",num);
}
else
{
num = num ^ 0xFFFF;
printf("The 1s complement is %d\n",num);
}
return 0;
}
1s compliment of 6 == 1. your code is returning 9.. since you are taking six as 0110 and then inverting the bits == 1001.
If the number,n, is an exact power of two, return n-1
- alex January 31, 2013else find the nearest power of 2 to the number, find their difference,d, and return d-1
also, if n=0 return 1
ex: n=14
nearest power=16
d=16-14=2
return d-1=1
if n=16, since it is an exact power of 2, return 16-1=15