7

Given two GUIDs, A and B, I perform C = A ^ B. Is the result a GUID?

(If so, I can use that instead of generating a third guid to represent an object that contains the two objects represented by A and B.)

i_am_jorf
  • 53,608
  • 15
  • 131
  • 222
  • How are you getting the first two GUIDs? And where did you get the hint that it might generate a GUID? – Bibhas Debnath Jan 20 '14 at 18:35
  • Related: [How to Combine Two GUID Values](http://stackoverflow.com/questions/1383030/how-to-combine-two-guid-values) – herohuyongtao Jan 20 '14 at 18:36
  • You can do so by XOR their data separately and then combine them together. It maybe not unique though. – herohuyongtao Jan 20 '14 at 18:41
  • Bibhas: I'm calling whatever function the OS provides for getting guids, so `CFGimmeAGuid` or `CoCreateMeAGuid` or whatever. The idea just naturally occurred to me. Herohuyongtao: I read that before asking. It's a different sort of thing he's doing there altogether. I realize I can XOR them together, thanks. – i_am_jorf Jan 20 '14 at 19:13

3 Answers3

12

A GUID is nothing but a uniform random number in the range of 0 to 2128 - 1. From a theoretical perspective, there is nothing which guarantees they are ever unique, but as this question keenly demonstrates, GUIDs are unique in practice due to the extremely low likelihood of a collision.

Given that there are only two requirements to meet: 1) range and 2) uniform randomness, it is easy to prove that the XOR of two GUIDs is indeed a GUID.

Imagine if GUID's were only two bits, then we can examine all possible scenarios:

 ^  00  01  10  11
00  00  01  10  11
01  01  00  11  10
10  10  11  00  01
11  11  10  01  00

All possible results 1) have the same range of 00 to 11, and 2) are equally likely to occur.

The only exception to this rule would be if one of the two source GUIDs is all zeros, causing the resulting XOR to produce a collision with the other.

Note that XOR is not the only operation to have this ability - adding two GUIDs and truncating the overflow bit also produces a GUID.

I wanted to amend clarification regarding UUID/GUID specifications which include a number of fixed bits.

Although there is no official, single definition of a "GUID", it conventionally is assumed to mean an RFC4122 UUID v4.

In the specification, all bits are random except:

  • 4 most-significant bits of byte 7 are 0100
  • 2 most-significant bits of byte 9 are 10

Performing an XOR on two UUIDv4's will not create another UUIDv4 unless you reset those bits as a post operation:

C = A ^ B | 00000000-0000-4000-8000-000000000000

With this adjustment, the result C will be a well-formed GUID as commonly defined.

Summary

I still stand by the original answer, but with some clarification:

The XOR of the random bits of two GUIDs results in a GUID.

E_net4
  • 27,810
  • 13
  • 101
  • 139
nicholas
  • 2,969
  • 20
  • 39
  • 2
    Yes, but... back in the bad ol' days, GUIDs were built from (possibly) several inputs - only part of which was uniformly random (inasmuch as random could be modeled). GUIDs were supposed to use the first three bits of the first byte to indicate the sources. Don't know if this is still common practice. Wikipedia [says](https://en.wikipedia.org/wiki/Globally_unique_identifier) that a random-source GUID should still contain 6 fixed bits - still a nice large distribution - but this complicates canonical combinatorials just a touch. You should probably restore the 6 fixed bits after combining. – Clay Jul 18 '15 at 14:32
  • @Clay, its been a few years, but somehow this answer still gets me some rep movement. Finally decided to add clarification per your suggestion on the non-random fixed 6 bits. – nicholas Dec 13 '21 at 20:17
  • that's excellent. This was one of the first questions I ever answered on SO...and I didn't really know how to do an answer...back it up with research, etc. I certainly didn't drill into the bits as you've done here. Very good! – Clay Dec 14 '21 at 12:50
  • Does anything/anyone in practice care about the canonical bits? Is anything - for example a Microsoft COM library or SQL Server using the `uniqueidentifier` data type - going to reject a value if it doesn't conform to UUID v4? – Emperor Eto Jul 25 '23 at 12:31
4

A year and a half later - and contradictory to boot - but I think the answer is "probably not". A canonical GUID has structure and parts of that structure will get messed up by XORing two GUIDs. There are bits in a GUID that describe the source as described here.

There were privacy issues that arose from early GUID generators that used MAC addresses as part of the scheme, and most applications have turned to randomizing GUID generators... but there are outlying exceptions. For example, you can get SQL Server to generate "sequential" GUIDs (which sounds bad, but there is decent reasoning behind it).

There are also standard ways of turning URLs into GUIDs. The idea here is that everybody that does it does it the same way - and so GUID-to-URL mapping can be done in a standard way - and lookup functions can be optimized around this standard mapping. You can find more here.

I'm sure many home-rolled GUID generators don't respect the GUID type fields and are therefore producing values that aren't technically valid GUIDs.

So, assuming two canonical random-sourced GUIDs are XOR'd together, the result is that the type indicator fields would be zeroed out. The type bits should really be ORed back into place. If one or both of the GUIDs were built from other sources, it gets a little uglier.

Community
  • 1
  • 1
Clay
  • 4,999
  • 1
  • 28
  • 45
1

Is the result a GUID

If you treat a guid as a 128-bit number, then sure, you can XOR the bits and create a new Guid that represents those bits. It's still "unique" in the sense that there's only one Guid represented by that 128-bit sequence. And the distribution of the results will be as uniform as the inputs, since the XOR function applied to a "random" set of inputs generates the same distribution as its inputs.

D Stanley
  • 149,601
  • 11
  • 178
  • 240