CODEWITHSUNDEEP
cbit-manipulation
The Flying Dutchman
The Flying Dutchman

Reputation: 592

Combining two integers with bit-shifting

I am writing a program, I have to store the distances between pairs of numbers in a hash table.

I will be given a Range R. Let's say the range is 5. Now I have to find distances between the following pairs:

1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

that is, the total number of pairs is (R^2/2 -R). I want to store it in a hash table. All these are unsigned integers. So there are 32 bits. My idea was that, I take an unsigned long (64 bits).
Let's say I need to hash the distance between 1 and 5. Now

long k = 1;
k = k<<31;
k+=5;

Since I have 64 bits, I am storing the first number in the first 31 bits and the second number in the second 31 bits. This guarantees unique keys which can then be used for hashing.

But when I do this:

long k = 2;
k << 31;
k+= 2;

The value of k becomes zero.

I am not able to wrap my head around this shifting concept.

Essentially what I am trying to achieve is that,

An unsigned long has    | 32bits    |  32 bits  |
Store                   |1st integer|2nd integer|

How can I achieve this to get unique keys for each pair?

I am running the code on a 64 bit AMD Opteron processor. sizeof(ulong) returns 8. So it is 64 bits. Do I need a long long in such a case?

Also I need to know if this will create unique keys? From my understanding , it does seem to create unique keys. But I would like a confirmation.

Upvotes: 1

Views: 4599

Answers (2)

clan
clan

Reputation: 96

The concept makes sense. As Oli has added, you want to shift by 32, not 31 - shifting by 31 will put it in the 31st bit, so if you shifted back to the right to try and get the first number you would end up with a bit missing, and the second number would be potentially huge because you could have put a 1 in the uppermost bit.

But if you want to do bit manipulation, I would do instead:

k = 1 << 32;
k = k|5;

It really should produce the same result though. Are you sure that long is 64 bits on your machine? This is not always the case (although it usually is, I think). If long is actually 32 bits, 2<<31 will result in 0.

How large is R? You can get away with a 32 bit sized variable if R doesn't go past 65535...

Upvotes: 2

Jerry Coffin
Jerry Coffin

Reputation: 490108

Assuming you're using C or something that follows vaguely similar rules, your problem is primarily with types.

long k = 2;  // This defines `k` a a long
k << 31;     // This (sort of) shifts k left, but still as a 32-bit long.

What you almost certainly want/need to do is convert k to a long long before you shift it left, so you're shifting in a 64-bit word.

unsigned long first_number = 2;
unsigned long long both_numbers = (unsigned long long)first_number << 32;
unsigned long second_number = 5;
both_numbers |= second_number;

In this case, if (for example) you print out both_numbers, in hexadecimal, you should get 0x0000000200000005.

Upvotes: 4

Related Questions