metsfan

ok so i got my first homework for my systems programming course and i feel like an idiot. ive been told that bitwise operations are easy, but i just cant seem to grasp it. i just have a few questions.

lets take this function we have to write for example:

/*
* sign - return 1 if positive, 0 if zero, and -1 if negative
* Examples: sign(130) = 1
* sign(-23) = -1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
*/

for the record, we cannot use any things such as if statements, switches, for loops, no control statements. the only thing we are allowed to use is the listed legal ops.

first of all, how are you supposed to be able to tell if a number is negative based on the bit pattern? if this were an unsigned integer, then -23 would be the same as (2^w)-1, assuming the word length is 8, this would be 233. but how does that help me determine if its negative? it doesnt, as far as i can see, and even so, it wouldnt help me determine if a number is negative, only if it is zero or nonzero.

i was thinking a possible way to do this would be to do the bit operation & on this with 256 (all ones), and then if there were any ones left, it would mean that the number was nonzero, if only zeros were left, then the number is zero. since we obviously cannot use if statments or for loops, the obvious choice would be to do the bitwise operation described above, then shift the bits over by one less than the number of bits on the original number. but without being able to use operations such as minus, divide, or modulo, how would i do determine the number of bits in the number?

also, what is this two's complement stuff? i dont remember going over this in lecture, but apparently i am expected to know what this is.

any help or tips would be apreciated in the general topic of bit operations in general. thank you very much in advance

MBirchmeier

My first suggestion would be to google two's compliment. It's not a hard concept, and it will come up often for digital courses. If you have specific questions I'll try to help, but 'I don't get X' doesn't help me help you learn it.

The next thing I'd do is determine your inputs and outputs, write them in binary (notation 2's compliment) for ease.

Finally I'd try to figure out how to get from the inputs to the outputs using the given functions.

-MBirchmeier

Kaja Fumei

I remember that lab. It's fun.

This might help:
http://www.cs.umd.edu/users/meesh/we...s/numbers.html

Benoit

To get two's compliment, just reverse the bits (1 to 0 and 0 to 1) and add 1, for example if you wanted to find -26 binary:

Remember that only signed numbers can be negative and this is a 16-bit example

26b = 0000000000011010

reverse the bits

1111111111100101

add 1

-26b = 1111111111100110

You can tell its negative because the sign bit (most significant bit, most left bit) is 1

This may seem a bit weird, but it all works out if you add the number and its two's complimnt

0000000000011010
1111111111100110
________________
0000000000000000

__________________
Johnny was a chemist's son but Johnny is no more, for what Johnny thought was H2O was H2SO4

metsfan

wow thanks a lot guys....im gonna go give it another try thanx a lot =)

MBirchmeier

I couldn't get this problem out of my head, so I went ahead and worked it out.

I got the answer down to 7 operations, using 1 additional variable. I'd be interrested to compare answers once the OP has things worked out.

-MBirchmeier

The Dark

I think you only need two ops, assuming you know the number of bits in an int (or if sizeof is allowed).

Kaja Fumei

When I did a similar lab (a lot of schools borrow it from CMU), you were to assume you were only dealing with 32 bit integers.

MBirchmeier

Only 2? There either's something I'm missing or something you're missing. I'd be interrested to see how that's done.

-MBirchmeier

DaWei

The ! operator rapidly converts any expression to 1 or 0.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers