Testing if the binary representation of an integer has an odd number of ones

Question

The fn odd_ones(x: u32) -> bool function should return true when x contains a odd number of 1s.

Assumption:

1. x is 32 bit unsigned.

Restriction:

1. The code should contain a total of at most 12 arithmetic, bitwise and logical operations.

Forbidden:

1. Conditionals, loops, function calls and macros.
2. Division, modulus and multiplication.
3. Relative comparison operators (<, >, <= and >=).

Allowed operations:

1. All bit level and logic operations.
2. Left and right shifts, but only with shift amounts between 0 and w - 1
3. Addition and subtraction.
4. Equality (==) and inequality (!=) tests.
5. Casting between u32 and i32.

---

My code: (Rust playground)

fn odd_ones(x: u32) -> bool {   
   let mid = (x >> 16) ^ x;
   let mid2 = (mid >> 8) ^ mid;
   let mid3 = (mid2 >> 4) ^ mid2;
   let mid4 = (mid3 >> 2) ^ mid3;

   (((mid4 >> 1) ^ mid4) & 1) == 1
}

fn odd_ones_test(x: u32) -> bool {    
    let sum = (0..32).map(|y| x >> y )
                     .fold(0, |sum ,y| sum + (y & 1));
    sum % 2 != 0
}

fn test (from: u32, to: u32) -> bool {
    (from..to).all(|x| odd_ones_test(x) == odd_ones(x))
}

fn main() {
    println!("{}", test(!0 - 45345, !0));   
}

Any better way of doing this?

Answer 1

Leveraging code that other people wrote is always a great idea. In this case, there is count_ones:

fn odd_ones(x: u32) -> bool {  
    x.count_ones() % 2 == 1
}

This method is a shim for the LLVM intrinsic @llvm.ctpop.i32, which seems likely to become the very optimized SSE4.2 popcnt instruction when available.

Beyond that, you have some poor indentation habits. Rust uses 4-space indents, not the 3 (?!?) spaces you have in your odd_ones function.

There should not be a space between a function name and the arguments, whether in the function definition or the function call. Your test method should be fixed.

Be consistent with your spacing on commas. No space before, one space after. |sum ,y| is just wrong.

You should give names to magic constants. A rogue 32 laying around doesn't mean anything. Give it a name like BITS_IN_U32. There's an unstable constant that you might be able to use someday.

When mapping and folding over an iterator, you might as well put all the mapping into the map call. There's no reason to do the bitwise-and in the fold.

I have no idea what !0 - 45345 is supposed to mean or why those particular values are useful. That's bad news when you try to understand this code in the future.

const BITS_IN_U32: usize = 32;

fn odd_ones(x: u32) -> bool {  
    x.count_ones() % 2 == 1
}

fn odd_ones_test(x: u32) -> bool {    
    let sum = 
        (0..BITS_IN_U32)
        .map(|y| (x >> y) & 1)
        .fold(0, |sum, y| sum + y);
    sum % 2 != 0
}

fn test(from: u32, to: u32) -> bool {
    (from..to).all(|x| odd_ones_test(x) == odd_ones(x))
}

fn main() {
    println!("{}", test(!0 - 45345, !0));   
}

Answer 2

Once I had to count the bits that were set in an array of one million integers. After several naive(very slow) starts I came across some bit twiddling hacks that sped things up dramatically. This is a C# function that contains two methods.

private bool isOddOnes(UInt32 numToCheck)
{
    //first  method
    //Dim bitsSetCt As UInt32 = 0
    //numToCheck = numToCheck - ((numToCheck >> 1) And &H55555555UI)
    //numToCheck = (numToCheck And &H33333333UI) + ((numToCheck >> 2) And &H33333333UI)
    //bitsSetCt = ((numToCheck + (numToCheck >> 4) And &HF0F0F0FUI) * &H1010101UI) >> 24

    //second method
    UInt32 bitsSetCt = default(UInt32);
    bitsSetCt = numToCheck - ((numToCheck >> 1) & 0x55555555u);
    bitsSetCt = ((bitsSetCt >> 2) & 0x33333333u) + (bitsSetCt & 0x33333333u);
    bitsSetCt = ((bitsSetCt >> 4) + bitsSetCt) & 0xf0f0f0fu;
    bitsSetCt = ((bitsSetCt >> 8) + bitsSetCt) & 0xff00ffu;
    bitsSetCt = ((bitsSetCt >> 16) + bitsSetCt) & 0xffffu;

    return (bitsSetCt & 1u) == 1u;
}

Answer 3

Since I already know a better way of doing this thanks to this link given by @glampert in the comments and none of the answers so far followed the rules, I will answer my own question to wrap things up:

fn odd_ones(x: u32) -> bool {
    let mut m = x ^ (x >> 16);
    m ^= m >> 8;
    m ^= m >> 4;
    m &= 0xf;
    ((0x6996 >> m) & 1) == 1
}

Using 0x6996 bit pattern saves up 2 operations. Also, the use of ^= makes the code more compact.