Effective way of removing the rightmost 1 bit in a u64 value taking care of zero

help
1

I want to create a function which gets a u64 value, removes the rightmost 1 bit of the value and returns the result.

I found that the following function could do that:

pub fn r(x: u64) -> u64 {
    x & (x - 1u64)
}

Howerer, when 0 is specified as a value of the x parameter, the following overflow error occurs:

thread 'foo' panicked at 'attempt to subtract with overflow',

What is the effective way of avoiding the above overflow error?

I want to execute the above operation fast and effectively.

Introducing the if x == 0 { return 0; } can avoid above overflow error but I want to know if there's more effective way to resolve the issue.

Thanks.

1 Like
2

You can just mask all the other bits in the u64 using u64:MAX like so:

fn r(x: u64) -> u64 {
    x & (std::u64::MAX - 1)
}

This works for r(0): Rust Playground

As Michael-F-Bryan notes below, !1 is a shorter way of writing the same thing.

In both cases, it is optimized to a single instruction:

and rax, -2

So you can use whichever form you prefer with no cost.

2 Likes
3

You're just trying to apply a bitmask which will clear the right-most (least significant) bit, aren't you? Does x & !1 work?

2 Likes
4

@bradfier @Michael-F-Bryan Thanks for your reply. I'm so sorry but I meant that I wanted to remove the rightmost "1" bit in a u64 value.

For example, when the parameter x is

0b00000000_00000000_00000000_00000000_00000000_00000000_00000011_00000000u64

then, I want to return the value of

0b00000000_00000000_00000000_00000000_00000000_00000000_00000010_00000000u64

I'm so sorry in the lack of explanation.

5

In that case I would use u64::trailing_zeros

The intuitive implementation would be

fn r(x: u64) -> u64 {
    x & !(1 << x.trailing_zeros())
}

But unfortunately that gives an error in Debug mode for x = 0 because shifting a u64 left 64 times is checked and disallowed, although it works fine if compiled in Release mode.

One solution is to use the explicit operator u64::wrapping_shl

fn r(x: u64) -> u64 {
    x & !(1u64.wrapping_shl(x.trailing_zeros()))
}

The edge case for 0 is where this is not strictly correct. If x.trailing_zeros() == 64 then this code will perform x & 0b0...0001 rather than x & 0b0..0000, as the 1 is wrapped around.

However since the end result is the same I think it's acceptable.

Snippet: Rust Playground
Godbolt: Compiler Explorer

3 Likes
6

You are almost there.

In debug mode, Rust checks for numeric overflows on integers operations. This is why it panics when evaluating 0 - 1. You can opt-in for wrapping operations instead, by using the explicit wrapping_* methods.

x & (x.wrapping_sub(1))
6 Likes
7

@bradfier @olivren Thanks for your replies. x & x.wrapping_sub(1) looks good and I'll use it.

Thank you very much for your cooperation!

8

Looks like @keijiyoshida has a solution, but one other way to solve the '0' problem is to use

x & !(1 << x.trailing_zeros() % 64)

This should also do the trick--for the cost of a divide operation, this will turn the 64 case into a 0, so you won't get the overflow error.

2 Likes
9

Thanks a lot for your another solution!

1 Like
10

@U007D Actually you can replace the division with the usually cheaper masking using & 0x3F (Though tbh I won't be surprised if the compiler does it already)

2 Likes
11

@Gilnaa

x & !(1 << x.trailing_zeros() & 0x3f)

is even better since we avoid the divide, nice!

1 Like
12

Simply test for 0.

Your code is efficient and simple, but it obviously fails for the case x==0 because it should. There is no 1-bit in zero, so what do you want it to do?

So my "solution" is:

pub fn r(x: u64) -> u64 {
    if x==0 {0} else {x & (x - 1)}
}

This gives you the opportunity to do something else when x==0, if you like.

By the by, this reminds me of a simple program (which I think can be attributed to Christopher Strachey, c. 1960s):

fn nb(mut x: u64) -> usize {
    let mut n = 0;
    while x != 0 {
        x = x & (x - 1);
        n = n + 1;
    }
    n
}

It was often set as a puzzle to newcomers to see if they could explain what nb(x) was calculating.

PS: I was trying to write while x!=0 { (x,n) = (x&(x-1), n+1); } but of course I can't do that in Rust, can I?

1 Like
13

Counting the number of bits set, right? I almost thought it was hamming distance, of course that would be more like,

fn ham(x: u64, y: u64) -> usize {
   let mut n = 0;
   let mut x = x ^ y;
   while x != 0 {
     x &= x - 1;
     n += 1;
   }
  n
}
14

I almost thought it was hamming distance

Counting ones is the same as computing the hamming distance with zero, so it's technically a hamming distance too :slight_smile:

15

Yes. nb was chosen as the name as a (humorous) hidden clue: it counts the "number of bits".