CODEWITHSUNDEEP
c++bit-manipulationbitwise-operatorsuint32
johny
johny

Reputation: 13

C++ - Given multiple binary strings, produce binary string where n-th bit is set if in all given strings is n-th bit same

On input I am given multiple uint32_t numbers, which are in fact binary strings of length 32. I want to produce binary string ( a.k.a. another uint32_t number ) where n-th bit is set to 1 if n-th bit in every given string from input is same.

Here is simple example with 4 bit string ( just more simple instance of same problem ) :

input: 0011, 0101, 0110

output: 1000

because: first bit is same in every string on input, therfore first bit in output will be set to 1 and 2nd,3rd and 4th will be set to 0 because they have different values.

What is the best way to produce output from given input? I know that I need to use bitwise operators but I don't know which of them and in which order.

uint32_t getResult( const vector< uint32_t > & data ){
    //todo
}

Upvotes: 0

Views: 343

Answers (2)

Some programmer dude
Some programmer dude

Reputation: 409166

First of all you need to loop over the vector, of course.

Then we can use XOR of the current element and the next element. Save the result.

For the next iteration, do the same: XOR of current element with the next element. But then bitwise OR with the saved result of the previous iteration. Save this result. Then continue with this until you have iterated over all (minus one) elements.

The saved result is the complement of the what you want.

Taking your example numbers (0011, 0101 and 0110) then the first iteration we have 0011 ^ 0101 which results in 0110. The next iteration we have 0101 ^ 0110 which results in 0011. Bitwise OR with the previous result (0110 | 0011) gives 0111. End of loop, and bitwise complement give the result 1000.

Upvotes: 2

Martin Bonner supports Monica
Martin Bonner supports Monica

Reputation: 28987

You want the bits where all the source bits are 1 and the bits where all the source bits are 0. Just AND the source values and the NOT of the source values, then OR the results.

uint32_t getResult( const vector< uint32_t > & data ){
    uint32_t bitsSet = ~0; 
    uint32_t bitsClear = ~0;
    for (uint32_t d : data) {
        bitsSet &= d;
        bitsClear &= ~d;
    }
    return bitsSet | bitsClear
}

Upvotes: 3

Related Questions