Problems

Given the inputs I={1,3,5}, return outputs O={3,5,1}. Meaning, given I=1, return O=3, and so on. These are the constraints imposed:

1. No extra memory other than ‘I’ should be used to process.
2. Only operators available are: &, |, ~, ^, », «, +, -.
3. No logical operators/if’s/for’s/while’s please.

For example, another variant of problem where I={3,7} and O={7,3} is easily solved by calculating I^4. Where, given I=3, we get I^4=3^4=7 and given I=7, we get I^4=7^4=3. We need a similar solution where I and O are represented by the above statement.

A good deal of analysis had provided us with multiple solutions. Here are they:

(((1 << (x >> 1)) & 3) << 1) | 1
(x ^ 6) >> (((x ^ 3) & 2) >> 1)  - [I like this for one reason: 6 = 3*2*1]
(107 >> ((x^1)|(x>>1))) & 7 - [A small trick, this is similar to array access :)]
(11 >> ((x>>1) ^ (x>>2))) & 7 - [Optimized small trick!]
(x ^ 5) ^ (7 >> (x >> 1)) - [Smallest till now :(]
((((x + 3) & 7) + 2) >> 1) | 1
(((x << 1) ^ ((x + 2) >> 1)) & 7) | 1
((((x >> 1) & 1) << 1) | ((~((x >> 1) & 1) & ~(((x >> 1) & 2) >> 1)) & 1))<< 1 | 1 - [Sughosh's friend]
(((((x >> 1) | 1) << (x>>1)) & 3) <<1) | 1  - [Sughosh]

Out of curiosity, a function can be defined which would give the above output:

f(x) = (1 + Pow(2, 1 + floor(x, 2))) mod 8 (or simply as, f(x) = (x + 2) mod 6)

Which gives f(1) = 3, f(3) = 5, f(5) = 1

Supplementary Questions The above question had inspired us to form few other questions like this:

• Formulate for 1→3→5→7→1. Answers are follows:

((x + 1) & 7 ) | 1
((x+2) & 7) ) - [Hari] 
((x << 1) & 7) ^ x  - [Hari]
((x << 1) & 6) ^ x  - [Hari]
 (x^(x<<1))&7   - [Sughosh]

• A kind of romantic question (just for fun!) 1→4→3→1. Here are the answers:

((x ^ 5) >> ((x & 2) >> 1)) ^ ((x | (x >> 1)) & 2)
(12 >> (x >> (((x >> 1) & 1) ^ 1))) & 7 [Interesting, yet a bit tricky :)]
(((((~((((i>>1)&2)>>1)|((i>>1)&1)))<<1)|(((i>>1)&2)>>1))<<1)|(((i&4)>>2)|((i&2)>>1)))&7 - [Sugosh]

There is a generic systematic way of producing such kind of results. The K-Map way! But, stop, the problem with K-Map is that, once the number of bits increases it becomes really hard to compress the solutions or simplify them! Moreover, im not very sure K-Map does give multiple solutions?

Given a number (8/16/32/64 bit, +/-ve or 0) find if its a zero-valued number. Pretty easy task isnt? But wait! Here are a few restrictions on that:

1. No logical operators should be used [!, >, >=, <, ⇐, &&, ||, ==]
2. No if’s/for’s/while’s etc.
3. Only operators allowed: [ &, |, ~, ^, +, -, », « ]

We actually have got an interesting solution: (Does this hold over all archs?)

(1 << x) & 1 - [Sughosh]

Others actually depend on the Sign-bit occurance, which has a limitation on the size of the type. (and as well as the endianess)?

((-x) & (0x80 << ((sizeof(x)-1)*8))) >> ((sizeof(x)*8)-1)