有没有办法在数学上改进这个C位函数？

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

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

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