开发者

Left bitwise rotation on variable without carry?

Let us have a task to do left-bitwise-rotation on variable a without carry in C++. I think, it would be much better to use assembly inline to perform this routine, isn't 开发者_开发知识库it?

For example, if we have a == 100 == 0b<a bunch of zeros>1100100, a LR 1 should provide 0b1001001 == 73 (i.e. not 0b11001000 == 200).

So, the question is: how the code below should be rewritten to fit the task above?

#include <stdio.h>

int main()
{
  long long a = 0;

  scanf("%ld", &a);

  // Here the left-shifting should be replaced with left-rotating
  printf("%ld\n", a << 1);

  return 0;
}


Shift-with-carry is meaningless in a high-level language (even C), because there's no way to read the carry flag (formerly the high bit) from such languages, except more inline assembly.

On the other hand, if you store the high bit to another variable (and also do a shift operation), the compiler may generate a shift-with-carry followed by add-carry or mov-carry to get it there. Compilers are also reasonably good at combining two instructions into multiply-add fused instructions.


Looking at your revised question, the operation you are trying to perform is completely unrelated to any shift-with-carry instruction available on common processors. Since you want to shift by one and then clear the most significant one bit, you might find the bsr instruction helpful, many compilers have intrinsic functions that give you access to this instruction from within C code.


It would certainly not be better to do inline assembly to do something as simple as a left-shift with carry. Any modern compiler will easily handle that and produce equivalent assembly to anything you hand wrote, plus would have the advantage of not becoming as platform dependent.


If you really want assembler then here is how rotate left 64 bit variable by one bit might look in Visual C++ (for GCC __asm is different). For comparison there is also implementation in C++. Of course this is 32-bit assembler.

unsigned long long rotate_left_64(unsigned long long n)
{  
    return (n << 1) | (n >> 63);
}

int main()
{
    unsigned long long a = 0xF0F0F0F0F0F0F0F0;

    std::cout << std::hex << rotate_left_64(a) << std::endl;

    __asm
    {
        lea ebx, a
        rol DWORD PTR [ebx], 1
        rcl DWORD PTR [ebx+4], 1
    }
    std::cout << std::hex << a << std::endl;
    return 0;
}
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜