## [C++] An Interesting Bit Array Example

Here is an interesting bit array task and its solution in C++ that I thought it’s worth to share with you.

You are given four integers values: *N, A, B,* and* C*. You need to use them in order to create the sequence called *bitArray* with the following pseudo-code:

Task: calculate the number of distinct integer in the *bitArray* sequence.

__Solution__

Input: four space separated integers on a single line, *N**, A, B**, *and *C* respectively.

Where* N = 32, A = 16, B = 16, C = 16*.

Output: one integer that denotes the number of distinct integer in the *bitArray* sequence equals* 7 *as we set *N, A, B, C *values.

Input read from the console:

Input read from the console:

four space separated integers on a single line,

*N, A, B,*and

*C*respectively.

__Output print to the console:__

One integer that denotes the number of distinct integer in the sequence called

*bitArray*

*.*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <algorithm> #include <iostream> constexpr unsigned exp = 31; // exponent constexpr unsigned twoToExp = 1u << exp; int solve_b_even(unsigned int n, int a, int b, int c) { if (b == 0) { if (a == c) { return 1; } return 2; } if (a == 0 && c == 0) { return 1; } int a1_minus_a0 = (b - 1) * a + c; int numr = exp - __builtin_popcount((a1_minus_a0 & -a1_minus_a0) - 1); int denomr = __builtin_popcount((b & -b) - 1); unsigned int m = numr / denomr + (numr % denomr == 0 ? 1 : 2); return std::min(m, n); } int solve_b_odd(unsigned int n, int a, int b, int c) { if (b == 1) { return c == 0 ? 1 : std::min(n, twoToExp / (c & -c)); } if (a == 0 && c == 0) { return 1; } unsigned int m = 1; int b_minus_1 = b - 1; int a1_minus_a0 = b_minus_1 * a + c; int b_to_m = b; int mask = (twoToExp * (b_minus_1 & -b_minus_1) / (a1_minus_a0 & -a1_minus_a0)) - 1; while (m < n && (b_to_m & mask) != 1) { b_to_m = b_to_m * b_to_m; m = m * 2; } return std::min(m, n); } int solve(unsigned int n, int a, int b, int c) { if (b % 2 == 0) { return solve_b_even(n, a, b, c); } return solve_b_odd(n, a, b, c); } int main() { // int n, a, b, c; int n = 32; int a = 16; int b = 16; int c = 16; // std::cin >> n >> a >> b >> c; std::cout << solve(n, a, b, c); return 0; } |

1 2 |
$ clang++ cpp_bit_array.cpp -o cpp_bit_array -Wall -Wextra -std=c++1z -pedantic $ 7 |

The number of distinct integer in the sequence will be 536870912 when we change the previously set integer values to:

1 2 3 4 5 6 7 |
int n = -90000000; int a = 160514480; int b = 526178425; int c = 1833883134; $ clang++ cpp_bit_array.cpp -o cpp_bit_array -Wall -Wextra -std=c++1z -pedantic $ 536870912 |