I was trying to find a function that fit the following formula:
我试图找到一个符合以下公式的函数:
f(0,0) = ( 0, 1)
f(0,1) = ( 2, 3)
f(0,2) = ( 4, 5)
f(0,3) = ( 6, 7)
f(0,4) = ( 8, 9)
f(0,5) = (10,11)
f(0,6) = (12,13)
f(0,7) = (14,15)
f(1,0) = ( 1, 2)
f(1,1) = ( 1, 3)
f(1,2) = ( 5, 6)
f(1,3) = ( 5, 7)
f(1,4) = ( 9,10)
f(1,5) = ( 9,11)
f(1,6) = (13,14)
f(1,7) = (13,15)
f(2,0) = ( 3, 4)
f(2,1) = ( 3, 5)
f(2,2) = ( 3, 6)
f(2,3) = ( 3, 7)
f(2,4) = (11,12)
f(2,5) = (11,13)
f(2,6) = (11,14)
f(2,7) = (11,15)
I ended up with the following:
我最终得到以下内容:
pair f(int a, int b){
int k = (b >> a << (a+1)) + (1<<a);
pair p = {k - 1, k + (b%(1<<a))};
return p;
};
There is a problem, though: the modulus operator is not implemented on the architecture I'm aiming and is, thus, making the code slow. Is there any solution that doesn't use it?
但是有一个问题:模数运算符没有在我所瞄准的架构上实现,因此使代码变慢。有没有不使用它的解决方案?
There is a snippet to quickly test the formula:
有一个片段可以快速测试公式:
#include <stdio.h>
typedef struct pair_ { int x; int y; } pair;
pair f(int a, int b){
int k = (b >> a << (a+1)) + (1<<a);
pair p = {k - 1, k + (b%(1<<a))};
return p;
};
int main(){
pair correct[4][16] = {{{0,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}},{{1,2},{1,3},{5,6},{5,7},{9,10},{9,11},{13,14},{13,15},{17,18},{17,19},{21,22},{21,23},{25,26},{25,27},{29,30},{29,31}},{{3,4},{3,5},{3,6},{3,7},{11,12},{11,13},{11,14},{11,15},{19,20},{19,21},{19,22},{19,23},{27,28},{27,29},{27,30},{27,31}},{{7,8},{7,9},{7,10},{7,11},{7,12},{7,13},{7,14},{7,15},{23,24},{23,25},{23,26},{23,27},{23,28},{23,29},{23,30},{23,31}}};
for (int i=0; i<3; ++i)
for (int j=0; j<8; ++j)
printf("f(%.2d,%.2d) = (%.2d,%.2d) | Correct: %d %d\n",
i,
j,
f(i,j).x,
f(i,j).y,
f(i,j).x == correct[i][j].x,
f(i,j).y == correct[i][j].y);
return 0;
};
2 个解决方案
#1
2
If the modulus you are talking about is.
如果您正在谈论的模数是。
b % (1u << a)
Then you are in good shape because it's always by power of 2. This expression is equivalent to:
然后你处于良好的状态,因为它始终是2的幂。这个表达式相当于:
b & ~(~0u << a)
The shift should be pretty fast. If you're using a processor with no barrel shifter, it might be faster to use a lookup table:
转变应该非常快。如果您使用的是没有桶形移位器的处理器,则使用查找表可能会更快:
b & mask[a]
Define mask
as
将面具定义为
static unsigned mask[] = {
~(~0u),
~(~0u << 1),
~(~0u << 2),
~(~0u << 3),
~(~0u << 4),
... skipping some entries
~(~0u << 30),
~(~0u << 31),
};
#2
3
There is a problem, though: the modulus operator is not implemented on the architecture I'm aiming and is, thus, making the code slow. Is there any solution that doesn't use it?
但是有一个问题:模数运算符没有在我所瞄准的架构上实现,因此使代码变慢。有没有不使用它的解决方案?
If this is the only modulo operator
如果这是唯一的模运算符
b % (1<<a)
it can be replaced with
它可以替换为
b & ((1<<a)-1)
pair f(int a, int b){
int k = (b >> a << (a+1)) + (1<<a);
pair p = { k - 1, k + (b & ((1<<a) - 1)) };
return p;
};
#1
2
If the modulus you are talking about is.
如果您正在谈论的模数是。
b % (1u << a)
Then you are in good shape because it's always by power of 2. This expression is equivalent to:
然后你处于良好的状态,因为它始终是2的幂。这个表达式相当于:
b & ~(~0u << a)
The shift should be pretty fast. If you're using a processor with no barrel shifter, it might be faster to use a lookup table:
转变应该非常快。如果您使用的是没有桶形移位器的处理器,则使用查找表可能会更快:
b & mask[a]
Define mask
as
将面具定义为
static unsigned mask[] = {
~(~0u),
~(~0u << 1),
~(~0u << 2),
~(~0u << 3),
~(~0u << 4),
... skipping some entries
~(~0u << 30),
~(~0u << 31),
};
#2
3
There is a problem, though: the modulus operator is not implemented on the architecture I'm aiming and is, thus, making the code slow. Is there any solution that doesn't use it?
但是有一个问题:模数运算符没有在我所瞄准的架构上实现,因此使代码变慢。有没有不使用它的解决方案?
If this is the only modulo operator
如果这是唯一的模运算符
b % (1<<a)
it can be replaced with
它可以替换为
b & ((1<<a)-1)
pair f(int a, int b){
int k = (b >> a << (a+1)) + (1<<a);
pair p = { k - 1, k + (b & ((1<<a) - 1)) };
return p;
};