Binary ternary bit magic

There is a classic task for interviews, often formulated as follows:

There is an array of natural numbers. Each of the numbers is present in the array exactly two times, and only one of the numbers does not have a pair. It is necessary to propose an algorithm that determines the number that does not have a pair in the minimum number of passes through the array.

I suppose no one will be offended if I immediately give the solution to the problem: a unique element will coincide with $$$xor$-sum of all elements of the array, calculated in linear time.

I propose to reflect on another variation of this problem. What if all the elements except the desired one are present in the array not in pairs, but in threes? How complicated will the solution be and will it remain linear?

---

Let's try to solve by analogy. $$$xor$came up because it has two remarkable properties (besides associativity and commutativity, of course):

1. $$$\ forall a: a \ oplus 0 = a$
2. $$$\ forall a: a \ oplus a = 0$

Symbol $$$\ oplus$in this record is the mathematical designation of the operation $$$xor$. Suppose for a moment that there is an operation $$$xor_3$satisfying similar properties:

1. $$$\ forall a: a \ oplus_3 0 = a$
2. $$$\ forall a: a \ oplus_3 a \ oplus_3 a = 0$

In this case $$$xor_3$- The sum of all the elements of the array would give the correct answer. Therefore, let's build such a function.

We all used to perceive $$$xor$as "bitwise exclusive or" (even the name chosen is suitable - eXclusive OR), but I propose to look at this operation from a slightly different angle - like "bitwise addition modulo 2". No wonder the character $$$\ oplus$so much like a plus.

It seems to have changed only the name, and thoughts appear completely different. The bit representation of integers is simply a representation in the binary positional number system. And if each bit is perceived as a number 0 or 1, then $$$xor$- this is exactly addition modulo two.

Following similar reasoning, as $$$xor_3$one can take the bitwise addition modulo 3 in the ternary number system. It will satisfy all necessary properties, it remains only to write an implementation.

---

I will reveal the secret of the title of the article. There is a fairly common way to encode numbers - the binary-decimal format. Its essence is that every 4 bits of data store one decimal digit of the number, which greatly facilitates the translation into string representation and back.

By analogy, storing each ternary digit separately in two data bits can be called binary-ternary number encoding. For example:

$$

$$47_ {10} = 101111_ {2} = 1202_ {3} = 01 \: 10 \: 00 \: 10 \: _ {2/3}$$

Understandably, storing a normal unsigned 32-bit integer will require more data. Namely, $$$2 \ cdot \ lceil {\ log_3 {(2 ^ {32} -1)}} \ rceil = 2 \ cdot \ lceil {20 {,} 189752114} \ rceil = $ 4$a bit of information that easily enters the 64-bit long type format.

The implementation of converting from binary to binary ternary format is quite clumsy - a normal cycle with reading / writing the necessary bits by offset:

 static long to3(int n) { long ln = ((long) n) & 0xFFFFFFFFL; long result = 0L; for (int offset = 0; ln != 0L; ln /= 3, offset += 2) { result |= (ln % 3) << offset; } return result; } 

 static int from3(long n) { long result = 0L; for (int offset = 40; offset >= 0; offset -= 2) { result = (result * 3) + ((n >> offset) & 0x3L); } return (int) result; } 

As for the operation $$$xor_3$, then a simple implementation is also available for it:

 static long xor3(long a, long b) { long result = 0L; for (int offset = 0; offset < 42; offset += 2) { long digit = ((a >> offset) & 0x3L) + ((b >> offset) & 0x3L); result |= (digit % 3) << offset; } return result; } 

She can already be tested (and she even works!), But I'm not happy with it.

You see, the "bit" functions usually look like this (this is a method from the Long class):

 public static long reverse(long i) { i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L; i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L; i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL; i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL; i = (i << 48) | ((i & 0xffff0000L) << 16) | ((i >>> 16) & 0xffff0000L) | (i >>> 48); return i; } 

I admire such code because it is probably super optimal and at first glance it is completely incomprehensible how it works. From such algorithms, I get a special pleasure.

That is why I will rewrite the xor3 implementation, getting rid of the cycles and conditions:

 static long xor3(long a, long b) { long o = a & b & 0xAAAAAAAAAAAAAAAAL; long c = (a + b) - (o << 1); long m = c & (c >>> 1) & 0x5555555555555555L; return (c & ~(m | m << 1)) | (o >>> 1); } 

Further explanations will follow what generally happens and how people get to this.

---

So, there is a task of simultaneous processing of the 21st pair of bits (it is possible and more), guided by the following rules:

$$$$ display $$ \ begin {array} {|} \ hline \ oplus_3 & 00 & 01 & 10 \\ hline 00 & 00 & 01 & 10 \ hline 01 & 01 & 10 & 00 \ hline 10 & 10 & 00 & 01 \ hline \ end {array} $$ display $$

The pair of bits "11" simply cannot be caught, since it would correspond to a discharge with a value of 3, which is not found in the ternary notation.

What happens if you simply add the arguments a and b ? This operation will preserve the “locality” of pairs of bits for almost all variants of input data. The only exception is the sum of 10 and 10 , which, when overflowed, will climb into the territory of the next pair.

There are two approaches to this problem - preventing or correcting the consequences. The second option is much simpler. From the resulting amount you just need to subtract all the overflow bits. They are located only where the high bits of each pair are equal to one. From here comes the first magic variable:

 long o = a & b & 0xAAAAAAAAAAAAAAAAL; 

A constant, seemingly incomprehensible, in binary representation looks extremely simple: 0b101010...10 . In it, the units are in one, skipping the least significant bit. This helps to cut off from the a & b all that we are not interested. By shifting o by 1 bit to the left, we just get all the overflow bits that appear when adding

 long c = (a + b) - (o << 1); 

The variable c stores a value that is very close to the result, but with errors:

1. It has a pair of bits 11 , which modulo 3 should be replaced by 00 .
2. All results of addition 10 and 10 are equal 00 , and should be 01 .

We correct these errors in order. Finding pairs of bits equal to 11 is not difficult, we have already done something very similar.

 long m = c & (c >>> 1) & 0x5555555555555555L; 

The magic constant here is nothing more than ~0xAAAAAAAAAAAAAAAAL , that is, the number in which the single bits are in one, starting with the youngest. Thus, in the value of m unit bits will be the low bits of the pairs corresponding to pairs 11 in the value of c .

Expression m | m << 1 m | m << 1 represents these pairs entirely. You can get rid of them now in two ways. Which one to choose is a matter of taste:

• c -= m | m << 1;
• c &= ~(m | m << 1);

Dealing with the last error is easy: you need to add bits where we added 10 and 10 . And they are exactly equal o >>> 1 . Therefore, the final code looks like this:

 return (c & ~(m | m << 1)) | (o >>> 1); 

---

But that is not all. Having got rid of the cycles and conditions in one of the functions, I completely forgot about the cycles and conditions in the two remaining ones - to3 and from3 . Is it possible to optimize them in this way?

Watching how to look. If you want to honestly translate into a ternary number system, you will have to divide / multiply by 3, then there is no way to go. But you can replace the operation itself with a more optimal one: to match another 32-bit binary number to a 32-bit binary number so that different binary numbers correspond to different binary numbers (such mappings are called injective), while the values ​​of binary and ternary numbers do not have to match .

For example, direct mapping of binary digits to ternary ( $$$11001_2 \ rightarrow 11001_3$). However, here the implementation will be still uncomfortable. The easiest option that comes to my mind is to place the even bits of int in one half of the values ​​of type long , and the odd ones of the type into the other. The code will be elementary:

 static long to3(int n) { long ln = ((long) n) & 0xFFFFFFFFL; return (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32; } static int from3(long n) { return (int) (n | n >>> 32); } 

Such methods and zainlaynit possible, and therefore the solution to the original problem will be as follows:

 static int find(int[] v) { long res = 0L; for (int n : v) { long ln = ((long) n) & 0xFFFFFFFFL; res = xor3(res, (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32); } return (int) (res | res >>> 32); } 

As you can see, it is not very difficult. I would even say that the code looks beautiful (although it needs explanations). Hope you share my opinion.

Thanks for attention!