如何生成这种数字模式？

Question

给定输入1-32如何生成以下输出？

进出

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 ......

编辑不是家庭作业..只是缺乏睡眠.

我在C#工作,但我一直在寻找一种与语言无关的算法.

编辑2提供更多背景...我有一个包含32个项目的数组,代表一个二维棋盘.我需要此算法的最后一部分在矢量和图形之间进行转换,其中索引在棋盘上的黑色方块上对齐.

最终守则:

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

Answer 1

假设您可以使用按位运算符,您可以检查具有相同输出的数字的共同点,在这种情况下,我更喜欢使用输入0-31,因为它更简单(您只需将1减去实际值)

你有什么？

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
...

如果你注意到第三位总是0在输出应该是1,反之亦然,那么1输出应该是很容易的2

所以:

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

编辑

正如评论所建议的,它也应该起作用

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

因为在某些语言(如C)中0会评估false和任何其他值true.我不确定它是否也适用于C#,因为我从未用该语言编程.当然,这不是一个与语言无关的答案,但它更优雅!

Answer 2

在C:

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

要么

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

或者在了解FogleBird之后:

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

或者在Steve Jessop的想法之后:

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

要么

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

C运算符优先级是邪恶的.使用我的代码作为坏例子:-)

Answer 3

你可以使用整数除法和模2(偶数奇数)的组合:有四个块,第一个,第三个,第五个块等依次产生1,第2个,第4个,第6个,依此类推2 .

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

div 应该是整数除法.

编辑:当然,将第一个mod转换为div

Answer 4

只是为了笑,这是一种技术,可以在编译时以任意方式将输入1..32映射到两个可能的输出:

// 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;
}

通过更改常量,您可以处理所需的任何输出模式.显然在你的情况下有一种模式,这意味着它可以更快地完成(因为不需要转换),但其他人已经做到了.此外,查找表更常见的是数组,但这不是必需的.