使用位操作的两个整数的十进制级联

Question

我想只使用位操作来连接两个整数,因为我需要尽可能多的效率.有各种答案可用,但它们不够快我想要的是只使用左移位等操作的实现.请指导我怎么做

例

int x=32;
int y=12;
int result=3212;

我正在和FPGA实现AES.我需要在我的系统上使用它来减少某些任务的时间消耗

Answer 1

最有效的方法可能与此类似:

uint32_t uintcat (uint32_t ms, uint32_t ls)
{
  uint32_t mult=1;

  do
  {
    mult *= 10; 
  } while(mult <= ls);

  return ms * mult + ls;
}

然后让编译器担心优化.可能没有太多可以改进,因为这是基础10,它与计算机的各种指令(例如移位)不能很好地相处.

编辑:基准测试

Intel i7-3770 2 3,4 GHz
OS: Windows 7/64
Mingw, GCC version 4.6.2
gcc -O3 -std=c99 -pedantic-errors -Wall

10 million random values, from 0 to 3276732767.

结果(近似值):

Algorithm 1: 60287 micro seconds
Algorithm 2: 65185 micro seconds

使用的基准代码:

#include <stdint.h>
#include <stdio.h>
#include <windows.h>
#include <time.h>

uint32_t uintcat (uint32_t ms, uint32_t ls)
{
  uint32_t mult=1;

  do
  {
    mult *= 10; 
  } while(mult <= ls);

  return ms * mult + ls;
}


uint32_t myConcat (uint32_t a, uint32_t b) {
    switch( (b >= 10000000) ? 7 : 
            (b >= 1000000) ? 6 : 
            (b >= 100000) ? 5 : 
            (b >= 10000) ? 4 : 
            (b >= 1000) ? 3 : 
            (b >= 100) ? 2 : 
            (b >= 10) ? 1 : 0 ) {
        case 1: return a*100+b; break;
        case 2: return a*1000+b; break;
        case 3: return a*10000+b; break;
        case 4: return a*100000+b; break;
        case 5: return a*1000000+b; break;
        case 6: return a*10000000+b; break;
        case 7: return a*100000000+b; break;

        default: return a*10+b; break;
    }
}


static LARGE_INTEGER freq;

static void print_benchmark_results (LARGE_INTEGER* start, LARGE_INTEGER* end)
{
  LARGE_INTEGER elapsed;

  elapsed.QuadPart = end->QuadPart - start->QuadPart;
  elapsed.QuadPart *= 1000000;
  elapsed.QuadPart /= freq.QuadPart;

  printf("%lu micro seconds", elapsed.QuadPart);
}

int main()
{
  const uint32_t TEST_N = 10000000;
  uint32_t* data1 = malloc (sizeof(uint32_t) * TEST_N);
  uint32_t* data2 = malloc (sizeof(uint32_t) * TEST_N);
  volatile uint32_t* result_algo1 = malloc (sizeof(uint32_t) * TEST_N);
  volatile uint32_t* result_algo2 = malloc (sizeof(uint32_t) * TEST_N);

  srand (time(NULL));
  // Mingw rand() apparently gives numbers up to 32767
  // worst case should therefore be 3,276,732,767

  // fill up random data in arrays
  for(uint32_t i=0; i<TEST_N; i++)
  {
    data1[i] = rand();
    data2[i] = rand();
  }


  QueryPerformanceFrequency(&freq); 


  LARGE_INTEGER start, end;

  // run algorithm 1
  QueryPerformanceCounter(&start);
  for(uint32_t i=0; i<TEST_N; i++)
  {
    result_algo1[i] = uintcat(data1[i], data2[i]);
  } 
  QueryPerformanceCounter(&end);

  // print results
  printf("Algorithm 1: ");
  print_benchmark_results(&start, &end);
  printf("\n");

  // run algorithm 2
  QueryPerformanceCounter(&start);
  for(uint32_t i=0; i<TEST_N; i++)
  {
    result_algo2[i] = myConcat(data1[i], data2[i]);
  } 
  QueryPerformanceCounter(&end);

  // print results
  printf("Algorithm 2: ");
  print_benchmark_results(&start, &end);
  printf("\n\n");


  // sanity check both algorithms against each other
  for(uint32_t i=0; i<TEST_N; i++)
  {
    if(result_algo1[i] != result_algo2[i])
    {
      printf("Results mismatch for %lu %lu. Expected: %lu%lu, algo1: %lu, algo2: %lu\n",
             data1[i], 
             data2[i],
             data1[i],
             data2[i],
             result_algo1[i],
             result_algo2[i]);
    }
  }


  // clean up
  free((void*)data1);
  free((void*)data2);
  free((void*)result_algo1);
  free((void*)result_algo2);
}

Answer 2

位操作使用数字的二进制表示.但是,您尝试实现的是以十进制表示法连接数字.请注意,连接十进制表示与连接二进制表示几乎没有关系.虽然理论上可以使用二进制运算来解决问题,但我相信它远非最有效的方法.