Function in c++ stl that can give me numbers with even number of set bits? Or the code/logic for it?
Is there a built in function in C++ STL that could provide me a list of numbers which have even number of set bits? For example 110 which is 6 has 2 set bits which is even number of set bits. Is there a function that could give a list of numbers like this? Or could someone tell me the code/ what would the logic be behind generating numbers with even number of set bits?
An easy to understand way to generate the numbers with an even Hamming weight is to loop over all the numbers, calculate their Hamming weights, and keep only the numbers for which it is even. This way the numbers are also generated in order.
There are other ways, especially if the order is not critical. For example, the formula x ^ (x >> 1)
could be used to map even numbers to numbers with even Hamming weight, and similarly the formula x ^ (x << 1)
could be used to map a "normal" integer (up to but excluding the numbers with their most significant bit set) to a corresponding integer with an even Hamming weight.
With both of those ways, the numbers are not produced in order, but they are produced with a "nicer" loop (less branchy, more amenable to auto-vectorization). Since there is such a nice correspondence from the index of an element in that list to the value, depending on the application you may be able to skip putting these numbers into a list at all, and instead generate them directly in the place where they are needed.