Do you remember the good old point-and-click adventures? They provided plenty of puzzles and riddles with a compelling narrative. I loved them, possibly because I love riddles, puzzles, and this sort of challenge. So I was super excited when my employer supported the initiative of a Coding-Riddle-of-the-Week contest. This is the second issue and I’m going to present it here.
Produce a program which increments an integer variable by a value of 1 without using sum or increment operators.
You are pretty free to choose whatever integer size and type you prefer (I would say, but bool), and whatever language you want. I stuck with C++ because it was quicker, but most of my solutions can be easily ported to other languages.
So, before continuing be sure to give some thought to this riddle to not spoil the fun.
Increasing an integer number without using the addition (symbol) is quite a challenge. After some brainstorming, I figured out the following directions –
- use algebra (hey, we studied it a life long… let’s put it to some use);
- use bit representation (a pattern of bits needs to be turned into another pattern);
- use reverse definition – find a number that when decremented results in the argument number.
- use other language constructs that allow some mathematics
Usual caveats hold – when trying to increment a signed int, you may stumble into an undefined behavior if the result would be greater than the larger number that can be represented using such a type.
If the type is unsigned then you don’t have a UB, but if you are thinking of int as a mathematical integer then you may be in for some surprises in comparisons.
But let’s start in the same order I found the solutions.
Everything is relative
This is the very first solution, a plus, according to algebra is just a pair of minus in disguise. – -1 = +1, so subtracting -1 is just as adding 1.
// Everything's relative
[[nodiscard]] int f0( int n ) noexcept
{
return n - - 1;
}
A pretty boring solution, so let’s try something more exotic.
Stringly Typed Language
Getting back to the meaning of integers, I remember from primary school that is something stemming from the cardinality of a set, therefore if I create a set with a number of items equal to the number to increment, then add an item and compute the cardinality I got the desired result.
I opted for std::string for no specific reason… well I thought it was the only container that could be built with a given number of items, but I was wrong, std::vector can do it as well.
Any character can be used since the content of the string is not relevant, but its length is.
#include <string>
// stringly typed language
[[nodiscard]] int f1( int n )
{
std::string s( n, ' ' );
s.append( " " );
return s.size();
}
This method is a bit heavy on resources, but with nowadays PC could be affordable. Not as boring as the previous one, but still not that exciting. Time for something different…
Meta-programming is always cool
C++ metaprogramming is as contorted as it could be, in comparison, INTERCAL is a model of simplicity and mindfulness, but I digress. So I just imagined that we want to compute the increment at compile time. Uninteresting as it may be, here you are the code:
template<int N>
[[nodiscard]] int f2()
{
struct T { char a[N]; char b; };
return sizeof( T );
}
This time the argument is not passed as a function parameter, but as a template parameter. So you need to call this function with f2<41>() to get the answer. The same code cannot be used to compute something that’s only known at run-time since you can’t pass a variable as a template argument.
This was funny, but the limitation about the run-time was a bit disappointing and this led me looking into bits.
Every bit counts
What’s an integer, but a sequence of bits? What is left of an electronic engineer in my soul still knows how to design an adder circuit with some logic gates. You take two bits (addition terms) and output two bits. The first bit is the result, while the latter is the carry. In schematics, it would look like:
You can design an increment by chaining several of such circuits. All ‘A’s ports are connected to operand bits, the first ‘B’ port is set to 1 (we want to add 1), next circuit ‘B’ is connected to the previous carry signal. The translation in software is quite straightforward.
// every bit counts
int f3( int n )
{
int carry = 1;
int result = 0;
int mask = 1;
do
{
int bit = (n&1);
result |= (bit ^ carry)*mask;
carry = bit & carry;
n >>= 1;
mask <<= 1;
}
while( n != 0 );
return result;
}
The most notable part is that the loop completes when there are no more ‘1’ bits in the argument. I picked this as an alternative to sweeping through all the bits of the operand since it is a slight optimization and also because the use of ‘+’, needed for incrementing the loop counter, is forbidden.
It’s a bit thing
While looking at the bits and reasoning about what is the meaning of increment, I noticed the following pattern –
| 0+1 | 1 |
| 01+1 | 10 |
| 011+1 | 100 |
| 0111+1 | 1000 |
| 01111+1 | 10000 |
That is, from left to right:
- if the bit is 1, then it gets flipped to 0 and the operation continues,
- if the bit is 0, then it gets flipped to 1 and the operation stops.
In other words, bits to the left of the first 0, are not affected by the increment. That sounds like an algorithm
// it's a bit thing.
int f4( int n )
{
int mask = 1;
while( (n & mask) == mask )
{
n ^= mask;
mask <<= 1;
}
return n | mask;
}
This is faster, on average, than the previous solution since the loop lasts stops at the first least significant bit at 0 in the operand, while the former code looped through all the bits.
Also, it is shorter and somewhat more readable.
Lucky
This is just a crazy solution, loosely inspired by the random sort algorithm. Since I know which relation must hold between the result and the operand (result – 1 == operand), I may look for numbers that satisfy this relationship. And where do I get these numbers from? Uh? Random generator, of course. Given an infinite time, for sure, I’ll get the right number
#include <random>
int f5( int n )
{
std::random_device dev;
std::mt19937 generator( dev() );
std::uniform_int_distribution<std::mt19937::result_type> dist( std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
while( true ) {
int result = dist(generator);
if( result-1 == n )
{
return result;
}
}
}
This is more hideous than what is needed because of the Uglification Principle that inspires C++ Evolution (given two solutions yielding the same result, pick the uglier one). On the other end, it is true that you can choose different RNG algorithms. An improvement that I left out for sake of brevity (and some sadism). is to further limit the range of the random numbers. Since you can’t add, you could double the number and search the result in the (n, 2n] range. Of course in the argument is 0, then it must be treated as a special case. Also, negative numbers require some care. But … trusting in luck must be blind as the luck herself 🙂
Algebra class
After looking into representation, let’s have a look at semantics. I remember an optimization for computing multiplications from just square lookup tables, sum, and subtraction, and halving (axb = ((a+b)2-(a-b)2)/4. Therefore I looked for some formula that involved somehow n, resulting in n+1.
The formula is from basic algebra: (a2-b2) = (a+b)(a-b), which means that a+1=(a2-1)/(a-1).
int f6( int n )
{
return (n*n-1)/(n-1);
}
That’s it, elegant, neat, tidy. Regretfully you must ensure that n*n does not overflow the integer type you are using. Also may have some trouble if n equals 1.
Pointers and arrays
The next exploring direction was to look if the language provides, i.e. is there any operation in the syntactic sugar of the language that I can exploit to get a sum or increment?
Yes indeed. The weird C equivalence between array and pointers requires that a[n] == *(a+n). So item accessing hides a sum (and a multiplication if you look under the hood). Let’s use it
int f7( int n )
{
auto const* ptr = reinterpret_cast<char const*>(n);
auto result = reinterpret_cast<uintptr_t>( &ptr[1] );
return result;
}
Ugly as it can be it is just turning integers into pointers and back. Strictly speaking, this is UB. Even if the pointer is not dereferenced, pointer math could rely on the fact that the pointer is well defined and the integer argument may not be such a value. I found more info in this here.
I don’t like this solution very much, but it is still a hack.
Don’t look down
Talking about lookup tables… a lookup table where at index n, n+1 is stored could easily solve the problem. The drawback is that this is really expensive for integers beyond 8 bits. int16_t and uint16_t require 2*216 = 128k (and that’s could be still acceptable), while int32_t and uint32_t require 4*232=16G. Also, you need to create the table… So I decided to just show the proof of concept using an uint8_t and a table computed outside the code.
// Don't look down
int f8( uint8_t n )
{
static uint8_t const next[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 0 };
return next[n];
}
(I didn’t even try to format the code O:-) ).
The Crab Move
This solution stems from the random search one, i.e. searching from a solution in the solution space, but this time with a better strategy – linear search from the highest integer number.
#include <limits>
// The crab move
int f9( uint8_t n )
{
int result = std::numeric_limits<uint8_t>::max();
while( result-1 != n )
{
result -= 1;
}
return result;
}
Now that I read this solution again, I think that many improvements can be done both to restrict the search space (according to the same thoughts on the random search) and to step from the linear search to a binary search. A binary search would take just 32 attempts in the worst case to figure out the next integer for int32_t.
Half right
Being right half of the time is better than never being right. That sounds a bit pretentious (and it is), but sometimes you just need to look at your problem from a different perspective to find that not all the constraints you think you have, are there for real.
// correct half of the times
int f10( int n )
{
return n | 1;
}
Yes if n is odd, then the answer is wrong, but it is always right when n is even.
Recursion is Cool
With all the fuzz on functional programming, I couldn’t miss a recursive solution. It took a while to figure out what could be the best approach for applying recursion, eventually, I came out with the following – if the number is even, then just set the least significant bit to one (see the previous solution) and we are done. If the number is odd, then look for an even number in the most significant bits and pads with 0 the right of the result.
int f11( int n )
{
if( n % 2 == 0 )
{
return n | 1;
}
return f11( n >> 1 ) << 1;
}
Although this function has a certain elegance I wouldn’t pick this as the most readable, I’m not that recursion-addicted. Also, note that this is not a tail recursion, but in the worst case it recurs just 32 times. Likely no problems with the stack.
Pass the test
Last solution devised by me is dubbed “Pass the test” and the idea is that it is better to be right at least once than never. So, if you know you are testing with a specific number, why not just check that input?
int f12( int n )
{
if( n == 41 ) return 42;
return 0;
}
Although I wouldn’t advise using code like this in production, it may be useful to force a test passing or to implement mock-ups.
Conclusions
What a ride! Very interesting stuff from an apparently simple challenge. Although my intention was just to explore the solution space, it turned out I won, so it is my time to propose the next C++ riddle of the week.