This is one of the free Hackerrank problems online:
You are given four integers: N, S, P, Q. You will use them in order to create the sequence with the following pseudo-code:
a[0] = S (modulo 2^31)
for i = 1 to N-1
a[i] = a[i-1]*P+Q (modulo 2^31)
Your task is to calculate the number of distinct integers in the sequence a.
I’m trying to understand solution #2
here. It works but I can’t figure out why — specifically, the insert() function:
unsigned long long mask[40000000];
unsigned insert(unsigned x) {
unsigned res = (mask[x >> 6] & (1ULL << (x & 0x3F))) == 0;
mask[x >> 6] |= 1ULL << (x & 0x3F);
return res;
}
It seems the mask array is meant to contain the previous values of X, but how does it do so if it right-shifts 6 bits of X’s value away — wouldn’t that mean multiple values of X will wind up being mapped to the same mask element? Also, what’s the significance of 6 bits (including the 0x3F which is 0b111111)?
Just wondering if this is some kind of cool idiom I’ve never seen before.
There’s another StackOverflow page about this Hackerrank problem but it was a totally unrelated question.
2
Also, what’s the significance of 6 bits (including the 0x3F which is 0b111111)?
A long long, in this environment, represents a 64-bit integer. Notice that 64 is 2^6. (as an aside I would prefer to use uint64_t from #include <cstdint> to be explicit about the number of bits)
It seems the mask array is meant to contain the previous values of X, but how does it do so if it right-shifts 6 bits of X’s value away — wouldn’t that mean multiple values of X will wind up being mapped to the same mask element?
Yes, each element of mask contains 64 elements in its 64 bits.
The expression mask[x >> 6] & (1ULL << (x & 0x3F)) does two things: First, it selects an element (a long long) of the mask array by indexing using all but the least significant six bits. Second, it uses (1ULL << (x & 0x3F) to set a single bit using the remaining six bits that were ignored when indexing into the mask array. Specifically, this takes a 1, and shifts it to the position given by (x & 0x3f) – i.e. the six bits of x that weren’t used to pick an array element.
mask[x >> 6] |= 1ULL << (x & 0x3F); likewise selects an element of mask using all-but-the-last six bits, and sets a single bit within it, as selected by the last six bits of x.
Just wondering if this is some kind of cool idiom I’ve never seen before.
A single, small value with bits having meaning would be called a “bit mask” or “bit field”. In the case of an array of values holding bits, I would call it a “bit set” (e.g. std::bitset or “bit array” (as a popular Rust library calls it).
There are also dynamic ones that can grow and shrink as needed; in many cases, your C++ standard library’s std::vector<bool> will be a specialization that uses this trick for storage.
3