How can I generate this pattern of numbers?

Question

Given inputs 1-32 how can I generate the below output?

in. out

1. 1
2. 1
3. 1
4. 1
5. 2
6. 2
7. 2
8. 2
9. 1
10. 1
11. 1
12. 1
13. 2
14. 2
15. 2
16. 2 ...

Edit Not Homework.. just lack of sleep.

I am working in C#, but I was looking for a language agnostic algorithm.

Edit 2 To provide a bit more background... I have an array of 32 items that represents a two dimensional checkerboard. I needed the last part of this algorithm to convert between the vector and the graph, where the index aligns on the black squares on the checkerboard.

Final Code:

 --Index;
 int row = Index >> 2;
 int col = 2 * Index - (((Index & 0x04) >> 2 == 1) ? 2 : 1);

Answer 1

Assuming that you can use bitwise operators you can check what the numbers with same output have in common, in this case I preferred using input 0-31 because it's simpler (you can just subtract 1 to actual values)

What you have?

0x0000 -> 1
0x0001 -> 1
0x0010 -> 1
0x0011 -> 1
0x0100 -> 2
0x0101 -> 2
0x0110 -> 2
0x0111 -> 2
0x1000 -> 1
0x1001 -> 1
0x1010 -> 1
0x1011 -> 1
0x1100 -> 2
...

It's quite easy if you notice that third bit is always 0 when output should be 1 and viceversa it's always 1 when output should be 2

so:

char codify(char input)
{
     return ((((input-1)&0x04)>>2 == 1)?(2):(1));
}

EDIT

As suggested by comment it should work also with

char codify(char input)
{
     return ((input-1 & 0x04)?(2):(1));
}

because in some languages (like C) 0 will evaluate to false and any other value to true. I'm not sure if it works in C# too because I've never programmed in that language. Of course this is not a language-agnostic answer but it's more C-elegant!

Answer 2

in C:

char output = "11112222"[input-1 & 7];

or

char output = (input-1 >> 2 & 1) + '1';

or after an idea of FogleBird:

char output = input - 1 & 4 ? '2' : '1';

or after an idea of Steve Jessop:

char output = '2' - (0x1e1e1e1e >> input & 1);

or

char output = "12"[input-1>>2&1];

C operator precedence is evil. Do use my code as bad examples :-)

Answer 3

You could use a combination of integer division and modulo 2 (even-odd): There are blocks of four, and the 1st, 3rd, 5th block and so on should result in 1, the 2nd, 4th, 6th and so on in 2.

s := ((n-1) div 4) mod 2;
return s + 1;

div is supposed to be integer division.

EDIT: Turned first mod into a div, of course

Answer 4

Just for laughs, here's a technique that maps inputs 1..32 to two possible outputs, in any arbitrary way known at compile time:

// binary 1111 0000 1111 0000 1111 0000 1111 0000
const uint32_t lu_table = 0xF0F0F0F0;

// select 1 bit out of the table
if (((1 << (input-1)) & lu_table) == 0) {
    return 1;
} else {
    return 2;
}

By changing the constant, you can handle whatever pattern of outputs you want. Obviously in your case there's a pattern which means it can probably be done faster (since no shift is needed), but everyone else already did that. Also, it's more common for a lookup table to be an array, but that's not necessary here.

Answer 5

The accepted answer return ((((input-1)&0x04)>>2 == 1)?(2):(1)); uses a branch while I would have just written:

return 1 + ((input-1) & 0x04 ) >> 2;