Unset the rightmost set bit

Question

Possible Duplicates:
How do you set, clear and toggle a single bit in C?
Removing lowest order bit

n is a positive integer. How can its rightmost set bit be unset?

Say n= 7 => n = 0111. I want 0110 as the output. Is there any simple bitwise hack to achieve the goal?

related, with explanation, both get & unset. [How to get position of right most set bit in C](https://stackoverflow.com/questions/31393100/how-to-get-position-of-right-most-set-bit-in-c/42747608#42747608) — qeatzy, Sep 16 '19 at 01:32

score 19 · Answer 1 · edited Jan 16 '11 at 05:39

19

Try n & (n-1) where & is bitwise AND

n = 7
n - 1 =6

n & (n-1)=> 0 1 1 1   (7)
          & 0 1 1 0   (6)
           --------- 
            0 1 1 0  (done!)

EDIT (in response to the comment given by Forest)

n = 6 
n - 1 = 5

n & (n-1)=> 0 1 1 0   (6)
          & 0 1 0 1   (5)
           --------- 
            0 1 0 0  (done!)

edited Jan 16 '11 at 05:39

Matthew Flaschen

278,309
50
514
539

answered Jan 16 '11 at 05:26

Prasoon Saurav

91,295
49
239
345

1

@taspeotis : Check out the question again " How can its rightmost **set** bit be unset?" – Prasoon Saurav Jan 16 '11 at 05:38
Ah, yes. I overlooked the word "set". – ʇsәɹoɈ Jan 16 '11 at 05:41
4

+1 Nice! I still don't understand how people see solutions like that so quickly. – Dawson Jan 16 '11 at 05:45
4

@Toolbox: Either we've seen them before or we spent our childhood inventing them. For me it's a bit of both. – Artelius Jan 16 '11 at 05:51
1

@Toolbox see Hacker's Delight (the book) – ergosys Jan 16 '11 at 05:54
This throws an error if the number is equal to INT_MIN – Himanshu Mittal Feb 07 '21 at 03:27

score 5 · Answer 2 · answered Jan 16 '11 at 05:45

Your question is unclear.

If you just want to unset bit 0, here are some methods (with slight variations in behavior depending on your types involved):

x &= -2;
x &= ~1;
x -= (x&1);

If you want to unset the lowest bit among the bits that are set, here are some ways:

x &= x-1;
x -= (x&-x);

Note that x&-x is equal to the lowest bit of x, at least when x is unsigned or twos complement. If you want to do any bit arithmetic like this, you should use only unsigned types, since signed types have implementation-defined behavior under bitwise operations.

"rightmost set bit" seems perfectly clear. It was just a poorly chosen example. — Matthew Flaschen, Jan 16 '11 at 05:48

score 1 · Answer 3 · answered Jan 16 '11 at 05:44

1

unsigned int clr_rm_set_bit(unsigned int n)
{
    unsigned int mask = 1;
    while(n & mask) {
        mask <<= 1;
    }
    return n & ~mask;
}

answered Jan 16 '11 at 05:44

Joe W

21
1

1

This is O(N) while Prasoon's is O(1). Also, you want something more like `while(!(n & mask))`, but even that doesn't work for `n = 0`. – Mike DeSimone Jan 16 '11 at 05:47
1

Actually this method (when correctly implemented) isn't `O(n)`. It's `O(log(n))`. And since n is bounded by the size of an unsigned int, you could also call it O(1). – Artelius Jan 16 '11 at 05:56
Right, should have bounds checked for n==0 and n < MAXINT (or whatever the correct constant is for that) At least I interpreted the question correctly – Joe W Jan 16 '11 at 05:56

Unset the rightmost set bit

3 Answers3

Linked