Bit manipulation

Turn off the last comsecutive run of 1s in a number

For eg

S = 39 in decimal = 100111 in binary

It should he converted to 100000.

How to do this. Please help.

You can just count the number of trailing 1’s and then just count times right and left shift it. Check my code below:

#include<stdio.h>

int main() { 
	int a = 39,b,count = 0;
	b = a;
	while(a&1){
		count++;
		a = a>>1;
	}
	b = ((b >> count) << count);
	printf("b = %d\n",b);
	
	return 0;
}
1 Like

@raj79: That’s what the OP is asking about, isn’t it ? from 39 to 32 by turning off the trailing 3 ones. If the OP wants the result is to be in binary, then 1 more statement is enough for it. You don’t need an array for bit manipulation you see, unless the number is very large that even a long long int cannot store it.

x&(x+1) is what you’re looking for.

EDIT: If there may be trailing zeroes after the last sequence of ones use
y = x|(x-1)
ans = y&(y+1)

6 Likes

An amazing catch there mate. 1’s complement. Didn’t come to my mind. This should be marked as a solution. Upvoted.

If we take case of 10 = 1010 (8+0+2+0) and 11=1011 (8+0+2+1). Then their and should be - 1010 = 10.

Did i do some mistake??? Also, the trick works for most cases i tested, how did you think of it??

1 Like

@vijju123 If you add 1 to a number, all trailing 1s will be converted to 0’s and the most significant bit will be 1 and since he is taking a bitwise AND in the end, the most significant bit will be set to 0 again. Very good approach for a constant time solution.

1 Like

It doesn’t work when there are trailing zeroes after the last sequence of ones. @shubham_genius, will you have such a case?

Thanks @utkalsinha , i appreciate the explanation.

@meooow , I see. I interpretted the Q in the sense that, in “10001111000” the last consecutive 1s are “1111”. Meaning I interpretted that there can be trailing 0. BTW, clever thinking in your constraints, that i must say!!