# Understanding Bitwise Manipulation in c

This is a discussion on Understanding Bitwise Manipulation in c within the C Programming forums, part of the General Programming Boards category; I'm having some problems with some concepts. Using no loops nor conditionals, I want to understand how to work with ...

1. ## Understanding Bitwise Manipulation in c

I'm having some problems with some concepts.

Using no loops nor conditionals, I want to understand how to work with bitwise manipulation using only these operations: <<, >>, +, |, ^, &, ~, !, =

Some things I wanted to do are:

1. Negate a number with int negate(int x), such as negate(4) returns -4
I'm not quite sure how to do the necessary two's complement in order to turn the number into a negative.

2. Extract byte n from word x with int getbyte(int x, int n), such as getbyte(0x12345678,1) will return 0x56
I'm not sure how to approach this.

3. Find if x <= y with int islessorequal(int x, int y), return 1 if true and 0 if false, such as islessorequal(3,5) should return 1
It sounds simple enough, but without "<=", it makes it a lot harder.

4. Convert from sign-magnitude to two's complement with int sm2tc(int x), where sm2tc(0x80000005) should return -5
I'm not sure how to approach this either.

5. Find if x is a power of 2 in ispower2(int x) and return 1 if true and 0 if false - as such where ispower2(16) returns 1 and ispower2(15) returns false
This I know would involve making sure the number contains only one bit with a 1, but I am not sure how to manipulate it without a conditional to discover that sole bit.

Most of these are more binary math-related problems rather than c problems, so it seems to make most sense to find the way to convert it with those limited 9 operations first before putting it in c.
_________________________________________________

Any help would be appreciated - thank you!

2. Two's complement is defined in terms of the bitwise operators (and +, which isn't bitwise but is on your list), so if you look up the definition you're in.

Do you know what & (as opposed to &&) does?

Number 3 sounds interesting (I almost posted something very similar to that in the contest board last week, now I'm glad I didn't). Work out on paper what you want to have happen. (Ditto 4 and 5.)

3. Originally Posted by MrWannabe
Most of these are more binary math-related problems rather than c problems, so it seems to make most sense to find the way to convert it with those limited 9 operations first before putting it in c.
You might as well just work in C; the bit operators are all transparent so it is like using a calculator.

Here is a partial solution to #1 which illustrates a use of two's compliment. It only works on positive numbers.
Code:
```#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
int x=1<<(sizeof(int)*8-1), y=x-1, z;
printf("Lowest int: %d  Highest int: %d\n",x,y);
if (argc<2) {
puts("Need a number");
return 0;
} else z=atoi(argv[1]);
z^=y; z|=x; z+=1;
printf("%d",z);
return 0;
}```
The line in red reveals the lowest and highest signed int values using two's compliment, which these are useful masks since the lowest one is this (for simplicity, I'm using a char scale, 8 bits):
10000000
Only the Most Significant Bit set, which is the sign. Unfortunately, you cannot just OR this with a positive number, since negative values proceed in reverse (-1 is 11111111). First, you must flip all but the MSB by using the highest int value, 01111111. In fact, this will be the lowest value minus 1, since the value cannot get any lower, it "wraps around" and becomes the highest positive value instead*.

This comes out as one less than the negative value, so we add 1 to it.

[root~/C] ./a.out 92345973
Lowest int: -2147483648 Highest int: 2147483647
-92345973

I should maybe clarify that by "using two's compliment" here I did not mean using the actual formula, ("The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two (specifically, from 2N for an N-bit two's complement") since you cannot use subtraction. I meant using "an awareness" of how a two's compliment number is stored in a computer (as a signed value).

Anyway, I am sure you will want those two masks for something

* you can also get that number using XOR, obviously, which might be better since you're not suppose to use subtraction.

4. Hmm! problem #3 is a really good one, and you know for sure that it can't use loops or conditionals if else etc?

5. Problem #3 isn't too difficult, and you can certainly do it without if-else conditionals or things like that . . .
Code:
```int islessorequal(int x, int y) {
return ((~x + 1) + y) >> 31 == 0;
}```
The ~x+1 negates x, so ((~x + 1) + y) is like (y-x). Then I just right-shift by 31 to remove all but the sign bit, and check if the sign bit is zero. If it is, y-x was positive, so y >= x, so x <= y, as desired.

There's lots of ways to do this, and I hope I haven't given anything away by posting this here . . .

 I should note that I'm not sure if the standard guarantees whether 0's will be shifted in or not with signed right-shift; but in this particular case, it doesn't matter if the number is zero-extended or sign-extended, because I'm just comparing with zero. Either the sign bit was clear, in which case the number will be zero, or it was set, it which case the number will be 1 or 0xffffffff or something . . . Anyway, you could always write it a little differently, using & instead of >>, for example. [/edit]

6. Originally Posted by dwks
Problem #3 isn't too difficult, and you can certainly do it without if-else conditionals or things like that . . .
Code:
```int islessorequal(int x, int y) {
return ((~x + 1) + y) >> 31 == 0;
}```
The above only works when x equals y, in all other cases ie "x != y" it doesn't. For instance, x < 0 and y > 0, the 2's complement of x ie (~x + 1) is positive and right shifting (31 times) gives zero; same goes for the case of 0 < x < y. When x > y > 0, the right shift is arithmetic (at least on my machine) resulting in -1. However that is machine dependent and the right shift may very well be logical on the o/p's machine. Lastly the equality operator "==" can't be used.

7. What? If x < 0 and y > 0, you want zero -- and that's what you claim you get. If 0 < x < y, you want zero -- and that's what you claim you get. When x > y > 0, we are right shifting a negative number; it is unspecified what the answer is, but there's only two choices -- it must be either arithmetic or logical; if logical you get 1, if arithmetic you get -1. Neither of those is zero -- and that's what you want.

I have no idea why you say the equality operator can't be used.

8. Whoops! mea culpa.

Totally missed the fact that the function differentiates only between x <= y (returns 1) and x > y (returns 0).
The equality operator isn't listed in the set of 9 operators that can be used by the o/p.
Not an issue (now that the mists have cleared - thanks to you) as it can be tweaked to return the logical inverse of the expression.
Code:
`return !(~x+1+y >> 31);`

9. Originally Posted by itCbitC
The equality operator isn't listed in the set of 9 operators that can be used by the o/p.
Ah got you. I saw = and somehow ran with it, but that doesn't actually fly.

10. The problem doesn't actually define the size of an integer.

Quzah.

11. Originally Posted by quzah
The problem doesn't actually define the size of an integer.

Quzah.
Explicitly, no. Implicitly:
Convert from sign-magnitude to two's complement with int sm2tc(int x), where sm2tc(0x80000005) should return -5
I'm not sure how to approach this either.

12. Originally Posted by quzah
The problem doesn't actually define the size of an integer.

Quzah.
Ditto!
2. Extract byte n from word x with int getbyte(int x, int n), such as getbyte(0x12345678,1) will return 0x56

13. Originally Posted by itCbitC
Whoops! mea culpa.

Totally missed the fact that the function differentiates only between x <= y (returns 1) and x > y (returns 0).
The equality operator isn't listed in the set of 9 operators that can be used by the o/p.
Not an issue (now that the mists have cleared - thanks to you) as it can be tweaked to return the logical inverse of the expression.
Code:
`return !(~x+1+y >> 31);`
There's one problem with that code. Right shifting negative integers is, as far as I know, undefined.
It might be defined just to be one result out of two, and for both it might be right, but I'm not sure about that.

14. Originally Posted by EVOEx
There's one problem with that code. Right shifting negative integers is, as far as I know, undefined.
It might be defined just to be one result out of two, and for both it might be right, but I'm not sure about that.
Not undefined, implementation-defined.

15. Originally Posted by tabstop
Not undefined, implementation-defined.
Sorry, that's what I mean. So what does that mean, according to the standard? Does it say anything on this? As in, maybe (-1 >> 2) be only a few values? Or may it return the same number, but any at all, every time? Or may it make the computer explode?

Page 1 of 2 12 Last
Popular pages Recent additions