Check if bit is only set once in a vector of int

I have a vector of uint16_t and I want to check if there is a bit which is only set in one vector. I then get its position within the vector as well as from the bit.

Let's say we have:

v[0] = 0100
v[1] = 0110
v[2] = 1001

I would like to know that ind = 1 and val = 2.

In clumsy code this would be like that:

#include 
#include 
#include 

const uint16_t N = 10;

int main() {
    // Create a dataset
    std::vector vec(N, (1 << 2) + (1 << 3));
    vec[3] = (1 << 5);
    vec[6] = (1 << 7);

    // loop over the values
    for (auto i = 0; i < 16; i++) { 
        uint16_t counter = 0,ind;

        // loop over the vector
        for (auto ii = 0; ii < N; ii++) { 
            if (vec[ii] & (1 << i)) {
                if (counter++ == 1) { break; }
                ind = ii;
            }
        } // vector loop

        // Do we only have a single value?
        if (counter == 1) {
            printf("%i @ %i\n",i,ind);
        }
    } // value loop
} // main

Is there a better way to do this? In case it matters using g++ with Ubuntu.

Let me start by pointing out problems in your code:

Wrong type

The type of your global constant N is uint16_t. There are several problems with this:

• as you are using cstdint the type should be std::uint16_t (because the C++ header provides them in the namespace std, this note should be applied to all instances of uint16_t in your code)

• you are using N to indicate the size of the std::vector but sizes are specified using std::size_t

• you are using uint16_t for the variables counter and ind, which are not related to the type. counter just counts, so you would be fine with std::size_t and ind is an index to a vector so it might be an std::size_t as well

Magic number

The loop boundary 16 in your code is related to the size of the type that is stored in the vector and offers possibilities for inconsistencies between the two. You should not rely on that, instead calculate it from the type:

int numberOfBitsPerEntry = sizeof(vec[0]) * CHAR_BIT;

And use that as loop boundary.

Variable names

While N is borderline (as soon as there are more then one containers it becomes ambiguous) the other variable names are not:

• i is about as generic as it can get for a loop counter variable. What it actually does is signify the index of the bit you are currently looking at, so how about: bitIndex

• ii just tells me that i was already taken and you temporarily forgot what was the next letter in the alphabet. This index actually walks through the std::vector's elements, so you might call it elementIndex (which is still too generic but I don't know what exactly is stored in the vector)

• counter has already some information but it still does not inform you what is counted, how about enabledBitsCounter or if you take the notion of arranging your elements above each other so that the bits with the same index form a column: columnBitsCounter (in that light elementIndex might be named rowIndex)

• ind (probably short for index) is just another generic name. It signifies the index of the element that is the only one that has a one bit in this column. columnWinnerRowIndex might be a bit too verbose but the general idea should be clear

• vec does not say much about the contents. By staying in the table metaphor we might choose rows as the new name

This is C++

You are using printf in C++ where there are better alternatives (at least typesafety wise). Also you haven't included cstdio or stdio.h where printf comes from.

As it is C++ I would pledge for std::cout instead:

std::cout << bitIndex << " @ " << columnWinnerRowIndex << "\n";

Algorithm

Now to the algorithm itself. You need to walk through every column and look at each row so there is not much to change on the loops. (Besides the fact that auto might be overkill for int variables)

However, I find the loop break unnecessary (avoid changing the flow of loops from within the body) and the counter too heavyweight.

Basically there are 3 states for a column:

• 0 one bits
• 1 one bit
• too many one bits

This would fit nicely into an enum:

enum ColumnState {
    NO_ONE_BITS,
    ONE_ONE_BIT,
    TOO_MANY_ONE_BITS
};

Your counter is replaced with this:

ColumnState columnState = NO_ONE_BITS;
    for(int rowIndex = 0; rowIndex < (int)rows.size() &&
                          columnState != TOO_MANY_ONE_BITS; ++rowIndex) {
        if(rows[rowIndex] & (1 << columnIndex)) {
            switch(columnState) {
            case NO_ONE_BITS:
                columnState = ONE_ONE_BIT;
                columnWinnerRowIndex = rowIndex;
                break;
            case ONE_ONE_BIT:
                columnState = TOO_MANY_ONE_BITS;
                break;
            default:
                assert(!"Invalid state");
            }
        }
    }

On second thought the enum looks too verbose and the main problem I had with the break was the counter++ == 1 part that is a bit mind bending. Reverting to a counter might be more readable:

int columnBitsCounter = 0;
    for(int rowIndex = 0; rowIndex  1) {
                break;
            }
             columnWinnerRowIndex = rowIndex;
        }
    }

Encapsulation

You might want to separate the logic of finding the column winners from the output code and the input. The signature of a function that allows this could be

std::vector findRowWinners(const std::vector &rows);

Where the result vector gives the winning row for each column or rows.size() if there is no winner in this column.

StackExchange Code Review Q#57655, answer score: 9