Discussion
What will be the output of the program?
#include <stdio.h>
int main()
{
int x = 10;
printf("%d", x & (x - 1));
return 0;
}Answer: C
Correct answer: 8
The expression x & (x - 1) is a well-known idiom: it clears the lowest set bit of x.
Here \( x = 10 \), which is 1010, so \( x - 1 = 9 \), which is 1001. Subtracting one flips the lowest set bit to 0 and turns every zero below it into a 1 - that is what borrowing does in binary. ANDing the two therefore agrees on everything above that bit and disagrees at it and below:
10 = 1 0 1 0
9 = 1 0 0 1
-----------
& = 1 0 0 0The result 1000 is 8.
The idiom has two common uses. Repeating it until the value reaches zero counts the set bits in as many steps as there are ones - Kernighan’s algorithm. And a single application testing x & (x - 1) == 0 identifies a power of two, since only those have exactly one bit set.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development