CODEWITHSUNDEEP
c++bit-manipulation
Vito Wu
Vito Wu

Reputation: 51

How to fast set 9 bits after all '1's in an 64 bit integer

I am writing a C++ program and require a function that sets all 9 bits to 1 after all existing '1's.

That is, I'm going to write a function void set10BitsFull(int64_t& n) that for an integer "int64_t n = 0b...1000000000...", set10BitsFull(n) transforms n to "0b...1111111111...".

(Update) Bits of the input integer are sparsely set to 1, and there are at least 10 bits distance between two 1. For an sample input 0x20000200, the expected output is 0x3FF003FF. There will be at least 9 bits 0 after the last 1. The leftmost 10 bits will always be zero.

Here is my implementation of this function

/**
 * Inline function that set 10 bits to 1 after each set 1
 * i.e.,
 * ......1000000000...... -> ......1111111111.......
 *
 * @param n
 *      pointer of input number
 */
inline void set10BitFull(int_fast64_t *n) {
    // n = 1000000000
    *n |= (*n >> 1); // n = 1100000000
    *n |= (*n >> 2) | (*n >> 4) | (*n >> 6) | (*n >> 8); // n = 1111111111
}

In main loop of the program these two lines of code will be frequently called, and in previous testing, the computation cost is extremely high. Hence I would like to seek an approach that takes less computation overhead (less cpu cycles to compute), and possible solutions might include:

Upvotes: 4

Views: 278

Answers (2)

Sander De Dycker
Sander De Dycker

Reputation: 16243

You could do something like :

constexpr uint_fast64_t set10BitFull(uint_fast64_t n) {
    return (n << 1) - (n >> 9);
}

That should work with all inputs you described, where there are at least 9 0 bits after every 1 bit.

Upvotes: 6

sklott
sklott

Reputation: 2849

First of all, you need to get rid of pointers, accessing memory is slowest operation processor will do. Second, you can decrease number of operations by constantly duplicating number of 1s.

I.e. something like this:

 n |= n >> 1;  // will porduce 1100000000
 n |= n >> 2;  // will produce 1111000000
 n |= n >> 4;  // will produce 1111111100
 n |= n >> 2;  // will produce 1111111111

Upvotes: 2

Related Questions