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. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    2

    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. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by MrWannabe View Post
    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.
    Last edited by MK27; 09-23-2009 at 09:24 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    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. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    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 . . .

    [edit] 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]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    Quote Originally Posted by dwks View Post
    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. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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. #8
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    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);
    Last edited by itCbitC; 09-24-2009 at 01:04 AM.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by itCbitC View Post
    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. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The problem doesn't actually define the size of an integer.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by quzah View Post
    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. #12
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    Quote Originally Posted by quzah View Post
    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. #13
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by itCbitC View Post
    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. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by EVOEx View Post
    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. #15
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by tabstop View Post
    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 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitwise (need help not answer)
    By MSF1981 in forum C Programming
    Replies: 5
    Last Post: 02-12-2009, 01:28 PM
  2. Bitwise Questions
    By someprogr in forum C Programming
    Replies: 8
    Last Post: 12-14-2008, 06:45 PM
  3. Bit Manipulation Questions
    By CPPNewbie in forum C++ Programming
    Replies: 7
    Last Post: 08-12-2003, 03:17 PM
  4. Characters into bitwise ints
    By Code Zer0 in forum C++ Programming
    Replies: 9
    Last Post: 04-24-2003, 09:34 AM
  5. bitwise shifts
    By sballew in forum C Programming
    Replies: 28
    Last Post: 12-01-2001, 12:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21