Bit manipulation

general
1

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.

2

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
3

@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.

4

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
5

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

6

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
7

@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
8

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

9

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!!