Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
683 views
in Technique[技术] by (71.8m points)

c - Implementing logical right shift using only "~ & ^ | + << >> =" operators and 20 operations

So I have an assignment that I have to code a function in c that uses only the bitwise operations of ~ , & , ^ , | , + , << , >> , and =. I have to use only 20 operations. And I am not allowed to use control structures such as, if-else , for, while, switch, or anything else that excutes code in conditional blocks. Also type casting is also out and the bytes that are not declared in the function header (which is given to me), are limited to 1 byte or 8 bit values; so I have hex 0 through FF.

The function I have to code is a logical right shift. So instead of the bits filling up with the sign bit they should fill up with 0's

This is what I have done:

int logicalShift(int x, int n) {
    int op=0xFFFFFFFF;
    int tcn=(~n+1);
    int sizeshift=0x20 & tcn;
    op=(op<<sizeshift);
    return ((x>>n) + (op));
}

This is what I expect to get ( for an x=0x80000000, and n=0x01) I expect to get 0x40000000 which is 1073741824 in decimal. This is what I get. However (for an x=0x80000000, and n=0x0 I expect to get 0x80000000, however I get 0x7fffffff which is my answer minus a bit. I could add a bit, but it messes up the first answer. So What am I doing wrong that I have one case but not the other. I have also tried.

int logicalShift(int x, int n) {
    int op=0xFFFFFFFF;
    int tcn=(~n+1);
    int sizeshift=0x20 & tcn;
    op=(op<<sizeshift);
    return ((x>>n) + (op  ^ ~n));
}

I thought that if I XOR the set of bits zeroing out the sign bits with all 1's for the 0 case I would end up with something that was not negative (aka) 0x7fffffff when it went through the compilers conversion to 2's complement. It ended up making it worse. Please set me in the right direction what should I consider and why?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The difference between logical and arithmetic shift are the bits shifted in from the left. To implement logical shift in terms of arithmetic you can do the arithmetic shift and then clear the new bits. In pseudo-code:

  1. Generate a mask that will clear the leftmost n bits when ANDed with the result.
  2. Shift right by n bits.
  3. AND the mask.

Using AND means you don't have to care what bits are shifted in. You just want to unconditionally set them to 0.

The question then is how to generate the mask. I'll leave that as an exercise for you.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...