CODEWITHSUNDEEP
c#algorithmc#-4.0uniquebit-manipulation
ZeNo
ZeNo

Reputation: 1658

C# bitwise manipulation for generating unique number

I am trying to generate unique values in c# with the help of DateTime ticks and and incrementing number. Pseudo code:

  1. Take last 43 significant bits from DateTime.Now ticks (lets name it A)
  2. Take last 21 bits from increasing sequence (lets name it 'B')
  3. Left shift 'A' 21 times (lets name it 'C')
  4. Do binary OR in A and C

I ran the test for generating 2 million number and inserting in database column which has unique constraint set and it ran successfully.

Here is the piece of code that does that:

    private static long _sequence = 1;
    public static long GetUniqueNumber()
        {
            const int timeShift = 21;            
            var dateTime = DateTime.Now.Ticks;
            const long dateTimeMask = ~(0L) >> timeShift; 
            const long sequenceMask = ((~(0L) >> (64 - timeShift))); 
            var seq = Interlocked.Increment(ref _sequence);
            var dateTimeNo = (dateTimeMask & dateTime) << timeShift;
            var seqNum = (seq & sequenceMask);    
            var num = dateTimeNo | seqNum;
            return num;
        }

I have two questions: 1. Is this logic good enough to generate unique numbers ? 2. I find that some generated numbers are '-ve' which I didn't understand.

Any help/suggestions/improvements are welcome.

Upvotes: 0

Views: 1151

Answers (2)

Apurv Gupta
Apurv Gupta

Reputation: 860

Negative numbers are due to implementation of long. As it is a signed number, if MSB that is bit 64 becomes '1' after the bit wise manipulation, the number will become negative. Nothing to worry about that.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1502286

Is this logic good enough to generate unique numbers

Unique across what scope? Across multiple computers/processes/AppDomains?, certainly not. Within a single AppDomain? Not really. Generating 2 million numbers is irrelevant - that's just testing that your sequence part works. (221 is just over 2 million.)

If you can call GetUniqueNumber 221+1 times within the granularity of DateTime.Now (which is likely to be ~10-15ms) then you'll get a repeat. Have you measured how fast your computed can call this?

Then there's the fact that those 43 bits will be repeated in 243 ticks' time... or at least would be if you had a sufficiently fine-grained clock. (And sooner or later the granularity will work against you.)

I find that some generated numbers are '-ve' which I didn't understand.

Whenever dateTimeNo has its top bit (out of 43) set, you'll end up with a long with the top bit set - which means it'll be negative.

EDIT: Also note that your shifting is broken. This:

const long dateTimeMask = ~(0L) >> timeShift;

is performed a sign-extended shift - so you're just ending up with ~0L.

In short: use Guid.NewGuid. It's what it's there for.

Upvotes: 6

Related Questions