You are not logged in. Please login at to post your questions!


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.

asked 30 Jun '17, 22:02

shubham_genius's gravatar image

accept rate: 10%

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)


answered 30 Jun '17, 23:01

meooow's gravatar image

6★meooow ♦
accept rate: 49%

edited 30 Jun '17, 23:20

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

(30 Jun '17, 23:06) utkalsinha6★

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

(30 Jun '17, 23:08) vijju123 ♦5★

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

(30 Jun '17, 23:12) utkalsinha6★

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

(30 Jun '17, 23:12) meooow ♦6★

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

(30 Jun '17, 23:18) vijju123 ♦5★

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


int main() { 
    int a = 39,b,count = 0;
    b = a;
        a = a>>1;
    b = ((b >> count) << count);
    printf("b = %d\n",b);

    return 0;

answered 30 Jun '17, 22:47

utkalsinha's gravatar image

accept rate: 13%

edited 30 Jun '17, 22:49

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

(30 Jun '17, 22:54) utkalsinha6★
Answer is hidden as author is suspended. Click here to view.

answered 30 Jun '17, 22:09

raj79's gravatar image

accept rate: 10%


The idea is correct but is there any bit manipulation way to do this?

(30 Jun '17, 22:14) shubham_genius0★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 30 Jun '17, 22:02

question was seen: 337 times

last updated: 30 Jun '17, 23:20