'bitwise operation' Thread RSS Feed

bitwise operation

Wed, 14 May 2008 13:06:57 -0700

This is an exercise out of The C Programming Language.
Write a function invert(x, p, n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed to 0 and vice versa), leaving the others unchanged.

I understand what they want but only have an idea of how to do it (something with the logical AND operator and one's compliment.
Can someone show me how to do this?

Re: bitwise operation

Thu, 15 May 2008 05:31:48 -0700

let's try to do this. suppose x = 1010 and you need to invert the rightmost bit, or least significant bit (LSB). first you need to know what is there, 0 or 1. notice the result when you do bitwise AND with 1:

b & 1 = b

where b is a binary digit. you get the bit back whenever you AND it with 1. so to determine what is the LSB, we need to AND 1 with the LSB. the 4 bit binary of decimal 1 is:

1 = 0001

The result:

x = 1010
1 = 0001
-------- (AND)
    0000

you get 0. so the LSB is 0. you would get a positive number if LSB was 1. to innvert this bit, you can now bitwise OR 1 to it:

x = 1010
1 = 0001
-------- (OR)
    1011

to determine the next bit, you can left shift 1 by 1 place. use the left shift operator:

b = 1;   //consider 4 bit integer
b <<= 1; //b now contain: 0010 in binary

now AND x and b:

x = 1010
b = 0010
-------- (AND)
    0010

now you get a positive number, which means the 2nd bit from right is 1. to invert it, simply apply

x = x & ~b;

beware that the result should be checked as unsigned integer. consider:

x = 1010
b = 1000
-------- (AND)
    1000

in 2's complement system (like todays most computers) the result is a negative number, unless you cast it as unsigned integer.

learn more about bitwise operators.

hope this helps.

~Donotalo()

Re: bitwise operation

Thu, 15 May 2008 11:51:32 -0700

I've read your post about a dozen times and it's helped but I still can't figure out exactly how to do this. Would this be inside a loop or will one command line do it?

: let's try to do this. suppose x = 1010 and you need to invert the
: rightmost bit, or least significant bit (LSB). first you need to
: know what is there, 0 or 1. notice the result when you do bitwise
: AND with 1:
:

: b & 1 = b
:

:
: where b is a binary digit. you get the bit back whenever you AND it
: with 1. so to determine what is the LSB, we need to AND 1 with the
: LSB. the 4 bit binary of decimal 1 is:
:

: 1 = 0001

:
: The result:

: 
: x = 1010
: 1 = 0001
: -------- (AND)
:     0000
:

:
: you get 0. so the LSB is 0. you would get a positive number if LSB
: was 1. to innvert this bit, you can now bitwise OR 1 to it:
:
: x = 1010
: 1 = 0001
: -------- (OR)
: 1011
: [/code]:
: to determine the next bit, you can left shift 1 by 1 place. use the
: left shift operator:
:
: b = 1; //consider 4 bit integer
: b <<= 1; //b now contain: 0010 in binary
: [/code]:
: now AND x and b:

: 
: x = 1010
: b = 0010
: -------- (AND)
:     0010
:

:
: now you get a positive number, which means the 2nd bit from right is
: 1. to invert it, simply apply
: x = x & ~b;[/code]:
: beware that the result should be checked as unsigned integer.
: consider:
:
: x = 1010
: b = 1000
: -------- (AND)
: 1000
: [/code]:
: in 2's complement system (like todays most computers) the result is
: a negative number, unless you cast it as unsigned integer.
:
: learn more about
: bit
: wise operators.
:
: hope this helps.
:

~Donotalo()

Re: bitwise operation

Thu, 15 May 2008 20:00:18 -0700

: I've read your post about a dozen times and it's helped but I still
: can't figure out exactly how to do this. Would this be inside a loop
: or will one command line do it?

apparently you need a loop. suppose you need to invert bit 3 (i am assuming the LSB is bit 0) to bit 6 of an 8 bit integer x:

x = 10101101

you need to start from bit 3, so you need a 1 in an integer at position 3. you can get it by

b = 1 << 3

now if you do

x & b

you can get what is at bit position 3 of x. so you can toggle it now according to my previous post. once toggled, you can left shift the 1 in b to get a 1 at bit position 4:

b <<= 1

now you can test and toggle bit position 4 of x. this way you need to continue 4 times (bit 3 to bit 6 in this example). you can use a loop to do that.

i'm able to implement invert(x, p, n) in a single statement:

//inverts n bits of x from position p
int invert(int x, int p, int n) {
	return	(<expression>);
}

so this is your second assignment. try to do it without a loop. :)

~Donotalo()

Re: bitwise operation

Fri, 16 May 2008 11:26:09 -0700

I figured out how to do the exercise with a loop but can't figure out how to do it without.

: : I've read your post about a dozen times and it's helped but I still
: : can't figure out exactly how to do this. Would this be inside a loop
: : or will one command line do it?
:
: apparently you need a loop. suppose you need to invert bit 3 (i am
: assuming the LSB is bit 0) to bit 6 of an 8 bit integer x:
:
: x = 10101101
: [/code]:
: you need to start from bit 3, so you need a 1 in an integer at
: position 3. you can get it by
:
: b = 1 << 3
: [/code]:
: now if you do

: 
: x & b
:

:
: you can get what is at bit position 3 of x. so you can toggle it now
: according to my previous post. once toggled, you can left shift the
: 1 in b to get a 1 at bit position 4:
:
: b <<= 1
: [/code]:
: now you can test and toggle bit position 4 of x. this way you need
: to continue 4 times (bit 3 to bit 6 in this example). you can use a
: loop to do that.
:
: i'm able to implement invert(x, p, n) in a single statement:

: 
: //inverts n bits of x from position p
: int invert(int x, int p, int n) {
: 	return	(<expression>);
: }
:

:
: so this is your second assignment. try to do it without a loop. :)
:

~Donotalo()