How do you achieve engineering excellence? We do this at Schindler by keeping engineers interested, motivated, and open to challenges. That’s why our Innovation Lab Lead’s idea for a weekly programming riddle was promptly supported and encouraged.
This programming challenge is open to all employees in the software development branch in our Milan hub. Although it was initially scheduled as one riddle per week, this timing was quickly relaxed to allow both for more pressing activities and to give for more time to devise interesting solutions.
The challenge I’m about to write about triggered my interest and offered several possible solutions.
This was the challenge:
Write a program which increments an integer variable by 1 without using sum or increment operators.
No other constraints were set, leaving you free to choose whatever integer size and type you prefer, 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 I continue, why not give some thought to this riddle first, so as not to spoil the fun. And come back later to continue reading the solutions I came up with.
Done? Then let’s start.
Increasing an integer number without using the addition (symbol) is quite a challenge. After some brainstorming, I figured out the following directions:
The usual caveats apply – when trying to increment a signed int, you may stumble into an undefined behavior (UB) [0] 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 an 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 order I found the solutions.
This was the very first solution. A plus, according to algebra, is just a pair of minuses in disguise. –(–1) = +1. So subtracting –1 is the same as adding 1.
This solution works, no doubt about it, but is not very interesting. We can do better.
Getting back to the true meaning of integers, from primary school, I remember that integers are introduced as a measure of the cardinality of a set [1]. 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 get the desired result.
For no specific reason, I opted for std::string. Initially I thought that in C++, the string 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, only its length is.
This method is a bit heavy on resources, but with nowadays PC could be affordable. Not as uninteresting as the previous one, but still not that exciting. Time for something different…
C++ meta-programming is as contorted as it could be. In comparison, INTERCAL[2] is a model of simplicity and mindfulness, but I digress. So, I just imagined that we want to compute the increment at compile time. Not very flexible, but here is the code:
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 fun, but the limitation with the run-time was a bit disappointing, and this led me looking into bits.
What’s an integer, but a sequence of bits? Despite so many years spent writing code, at the core, I’m still an electronic engineer. This part of me likes to solder stuff and prompted me to design some circuitry. A digital adder is a circuit that performs additions. 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 such circuits. All ‘A’ 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.
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 because the use of ‘+’, needed for incrementing the loop counter, is forbidden.
While looking at the bits and reasoning about what is the meaning of increment, I noticed the following pattern (in binary)
0+1 = 1
01+1 = 10
011+1 = 100
0111+1 = 1000
01111+1 = 10000
That is, from left to right:
In other words, bits to the left of the first 0 are not affected by the increment. That sounds like an algorithm.
This is faster, on average, than the previous solution, since the loop 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.
This is a really impractical solution, loosely inspired by the random shuffle sort algorithm [3] (which now I found out is called bogosort, permutation sort, stupid sort or even slow sort).
Since we know which relation must hold between the result and the operand (result – 1 == operand), you can look for numbers that satisfy this relationship. And these numbers can be obtained via random generation. Given an infinite time, for sure, you’ll get the number you were looking for. And there are solid mathematical foundations [4].
This is more unattractive than what is needed because of the Uglification Principle that so often seems to inspire the C++ Evolution (given two solutions yielding the same result, pick the uglier one). I’m talking of the random number generation that is way more convoluted than in C (and many of the other languages).
On the other hand, it is true that you can choose different RNG algorithms. If you are interested in speeding up this solution, you may 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, if the argument is 0, then it must be treated as a special case. Negative numbers also require some care.
After having looked into representation, let’s have a look at semantics. I remember an optimization for computing multiplications by just using square lookup tables, sum, and subtraction, and halving (ab = ((a+b)2-(a-b)2)/4 [5]). So, I looked for a formula that somehow involves n, resulting in n+1.
The formula I found is from basic algebra: (a2–b2) = (a+b)(a–b). Solving for a+b you find: a+b = (a2–b2)/(a–b), from which a+1=(a2–1)/(a–1).
That’s it, elegant, neat, tidy. The only caveat is that you must ensure that n*n does not overflow the integer type you are using. You also may have some trouble if n equals 1.
The next direction to explore was to look at exploiting different language constructs. In other words - 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 relationship between array and pointers in C language requires that a[n] == *(a+n). So, item access hides a sum (and a multiplication if you look under the hood). Let’s use it.
It may look complicated, but it is just turning integers into pointers and back again.
More precisely, I pretend n to be a pointer to const char. Of course, it is not, n is just an integer, but let’s handle it as it is a pointer. Since this is a pointer, I can use the array notation (ptr[1]) and get the address of the first element. Being ptr a pointer to a char, whose sizeof is 1, the address of the element at position 1, is the pointer value incremented by one. Now let’s take this pointer and pretend it is an integer again.
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 on this here [6].
I don’t like this solution very much, but it is still a way to obtain what we want. Also, it may be quite hard to port to other languages not so close to C.
Talking about lookup tables… a lookup table where at index n, the value n+1 is stored could easily solve the problem. The drawback is that this it becomes expensive for integers beyond 8 bits. int16_t and uint16_t require 2*216 = 128k (and that 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.
I leave using meta-programming to generate this table at compile time as an exercise to the reader.
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.
Many improvements can be done, such as restricting the search space (keeping in mind the considerations on the random search) or moving 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.
Being right half of the time is better than never being right. Maybe sometimes you just need to look at your problem from a different perspective to find that you don’t have all the constraints you think you have.
Yes if n is odd, then the answer is wrong, but it is always right when n is even.
You may consider this cheating, and in part it is, but sometimes a partial solution may work if the domain is properly constrained.
Given the momentum that functional programming is gaining in recent years, 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 up 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 pad with 0 to the right of the result.
Although this function has a certain elegance, I wouldn’t pick this as the most readable. Also, note that this is not a tail recursion, but in the worst case it recurs just 32 times. Likely not a problem for stocks nowadays.
Last devised solution 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?
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.
It is no secret that engineers love challenges and have fun in solving problems, but it would be an oversimplification stopping there.
Lateral thinking and problem solving are skills that need exercise, to be fit when you encounter a new problem or a new challenge. Knowing your tools and being able to change perspective are very valuable engineering virtues.
For sure, you are not going to use any of these code examples in production software. This is more like how athletes that train with many exercises that won’t be used or shown in their performance.
It is all about training and improving.
The other benefit I see is the working environment. When properly managed these challenges foster collaboration and team building, and helps in building a welcoming, friendly, and rich working environment.
So, how does your solution compare to these? If you want, let us know by sending it via email to: liftlab@schindler.com.
About the Author
Massimiliano Pagani started coding back in the 80s, when computers were laughably slow, never had enough RAM and used tape recorders as storage memory. Since then, he never stopped writing bugs and other features. He worked in the video game industry, had some exposure to server and service development, got fascinated by functional programming, and spent several years in writing firmware and embedded software. When he is struck by something he reckons interesting, and has enough spare time, he writes on his blog at https://www.maxpagani.org/.
References
[0] Undefined behavior: https://en.cppreference.com/w/cpp/language/ub
[1] Cardinality of a set: https://www.cuemath.com/algebra/cardinality/
[2] INTERCAL – the language with no pronounceable acronym: https://en.wikipedia.org/wiki/INTERCAL
[3] Random sort: https://en.wikipedia.org/wiki/Bogosort
[4] Random sort termination: https://en.wikipedia.org/wiki/Infinite_monkey_theorem
[5] Multiplication with lookup table: https://en.wikipedia.org/wiki/Multiplication_algorithm#Quarter_square_multiplication
[6] Cast pointer to int: https://stackoverflow.com/q/3567905/11010186