You are not logged in. Please login at www.codechef.com 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

0★shubham_genius
1206
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)

link

answered 30 Jun '17, 23:01

meooow's gravatar image

6★meooow ♦
6.0k413
accept rate: 47%

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) utkalsinha5★
1

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★
1

@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) utkalsinha5★

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:

#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;
}
link

answered 30 Jun '17, 22:47

utkalsinha's gravatar image

5★utkalsinha
723118
accept rate: 12%

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) utkalsinha5★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×307

question asked: 30 Jun '17, 22:02

question was seen: 282 times

last updated: 30 Jun '17, 23:20