Dealing with bits

This is a discussion on Dealing with bits within the C Programming forums, part of the General Programming Boards category; I had a problem writing the following function: /* * bitMask - Generate a mask consisting of all 1's * ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    3

    Dealing with bits

    I had a problem writing the following function:
    /*
    * bitMask - Generate a mask consisting of all 1's
    * lowbit and highbit
    * Examples: bitMask(5,3) = 0x38
    * Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
    * If lowbit > highbit, then mask should be all 0's
    Legal ops: ! ~ & ^ | + << >>
    * Max ops: 16
    * Rating: 3
    */

    I wrote this so far:
    Code:
    int bitMask(int highbit, int lowbit) {
      int PosOrNeg = highbit+(~lowbit+1);
      int sign = PosOrNeg >> 31;
    
      int endXOR = sign ^ ~0;
    
      int ANDwith = ~(0x1 << 31);
      int rshift = 32 + (~highbit + 1);
      ANDwith = ANDwith >> rshift;
      ANDwith = ANDwith << lowbit;
    
      endXOR = endXOR & ANDwith;
    
      int num= 0 ^ endXOR;
      return num;
    }
    I know it is very poor code and it doesn't seem to work when the low bit is 0 and/or high bit is 31 among other cases. Try as I might, I can't seem to be able to fix this problem. I think I'm going about this problem wrong. I know a lot of you guys are pros here so if you could point me in the right direction, many thanks to you!

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I'm not sure what it is you're trying to do here. If you pass it 5 and 3, are you trying to get:

    00000000 00000000 00000000 00111000

    IE: Everything from high to low is set to 1 and the rest zero? Or what?


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

  3. #3
    -AppearingOnThis..........
    Join Date
    May 2005
    Location
    Netherlands
    Posts
    44
    I'm probably assuming too much again somehow or other, but you could try
    Code:
    unsigned long bitMask(unsigned long high, unsigned long low)
    {
    	unsigned long out, t = ~0;
    	
    	out = (t << high) << 1;
    	out |= ~(t << low);
    	
    	return ~out;
    }
    where you essentially create the bit fields at the sides of the desired field, then invert the bits
    Last edited by SirNot; 10-02-2006 at 10:49 AM.

  4. #4
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    Doesn't work if high < low unfortunately.

  5. #5
    -AppearingOnThis..........
    Join Date
    May 2005
    Location
    Netherlands
    Posts
    44
    Oops, I didn't see that part of the specification...

  6. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    3
    I'll try to clarify on the directions. Since the function doesn't pass in an int to bit manipulate, I believe we initially start off with an int set to all 0;s; 32 0's since this code is expected to run on a 32-bit machine (machine is assumed to run 2's-complement BTW). When we pass in a lowbit and a highbit, the bits from lowbit and highbit (inclusive) of the int should now be set to 1. If the lowbit is greater than highbit, then the int should just remain as all 0's

    I'm also having some trouble with high<low. The only way I can seem to differentiate it is doing some form of (high + (~low +1)) to subtract them and find out the sign bit. Problem is I don't know what to do with this.

    Thanks for the attempts so far guys. I appreciate it.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    So initialize your variable at start to zero, preform an if check...
    Code:
    int foo( int bar, int baz )
    {
        int fbb = 0;
        if( baz < bar )
            ...play around with the bits...
        return fbb;
    }
    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    -AppearingOnThis..........
    Join Date
    May 2005
    Location
    Netherlands
    Posts
    44
    Well this would work on a compiler which pads negative signed ints with 1s when shifted to the right:
    Code:
    unsigned long getbitmask(unsigned long high, unsigned long low)
    {
    	unsigned long out, sign, t = ~0;
    	
    	sign = (signed long)(high + ~low + 1) >> ((sizeof(long) << 3) + t); //or 31 if this is going to be run on a system in which sizeof(long) = 4
    	
    	out = (t << high) << 1;
    	out |= ~(t << low);
    	
    	return ~(out | sign); //equivelent to ~out & ~sign;
    }
    quzah:
    Legal ops: ! ~ & ^ | + << >>
    Last edited by SirNot; 10-02-2006 at 11:35 AM.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    if is not an operator. It is a keyword. if you want to be picky, = is not in the list of allowed operators! You lose!


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

  10. #10
    -AppearingOnThis..........
    Join Date
    May 2005
    Location
    Netherlands
    Posts
    44
    Well I was actually refering to your '<' operator...

    And besides, you can still write the function without the assignment operator:
    Code:
    unsigned long getbitmask2(unsigned long high, unsigned long low)
    {
    	return ~(((~0 << high) << 1 | ~(~0 << low)) | ((signed long)(high + ~low + 1) >> 31));
    }
    Last edited by SirNot; 10-02-2006 at 01:15 PM.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Ah, well I suppose '<' is an operator after all then. Well good job on doing their homework anyway.


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

  12. #12
    Registered User
    Join Date
    Oct 2006
    Posts
    3
    I tried your solution SirNot and makes a lot of sense ORing the 3 different conditions. I am passing in signed ints to begin with for the low and high bits so casting the (high + ~low + 1) to a signed int was not needed for me. Thank you SirNot and everyone else.

    Oh and quzah, we had about 15 more of these to do, most of which I manage to figure out after a long time (I'm slow). I was just getting stuck on this one last night (brain stopped working I guess) and figured I'd post here. Anyways, thanks for all your help!

  13. #13
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Another take:
    Code:
    #include <stdio.h>
    #include "util.h" /* for bits_uint */
    
    int bitMask_(int highbit, int lowbit);
    
    /*******************************************************************************
     * bitMask - Generate a mask consisting of all 1's
     * lowbit and highbit
     * Examples: bitMask(5,3) = 0x38
     * Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
     * If lowbit > highbit, then mask should be all 0's
     * Legal ops: ! ~ & ^ | + << >>
     * Max ops: 16
     * Rating: 3
     */
    int bitMask(int highbit, int lowbit)
    {
        return (((~0 << lowbit) ^ ((~0 << highbit) << 1)) >> lowbit) << lowbit;
    }
    
    int main(void)
    {
        int i = 5, j = 3;
        printf("bitmask(%d,%d) = %x\n", i, j, bitMask_(i,j));
        i = 3, j = 5;
        printf("bitmask(%d,%d) = %x\n", i, j, bitMask_(i,j));
        return 0;
    }
    
    /*******************************************************************************
     * Program Output
    bitMask_(5,3) : a = 11111111111111111111111111111000
    bitMask_(5,3) : b = 11111111111111111111111111000000
    bitMask_(5,3) : c = 00000000000000000000000000111000
    bitMask_(5,3) : d = 00000000000000000000000000000111
    bitMask_(5,3) : e = 00000000000000000000000000111000
    bitmask(5,3) = 38
    bitMask_(3,5) : a = 11111111111111111111111111100000
    bitMask_(3,5) : b = 11111111111111111111111111110000
    bitMask_(3,5) : c = 00000000000000000000000000010000
    bitMask_(3,5) : d = 00000000000000000000000000000000
    bitMask_(3,5) : e = 00000000000000000000000000000000
    bitmask(3,5) = 0
     */
    
    /*******************************************************************************
     * Description:
     *    This function explains the other version "in slow motion".
     *    It uses the bits_uint function, implemented elsewhere, to show the bits.
     */
    int bitMask_(int highbit, int lowbit)
    {
        char binary[33];
        int a,b,c,d,e;
    
        a =  ~0 << lowbit;
        printf("bitMask_(%d,%d) : a = %s\n", highbit, lowbit, bits_uint(binary, a));
    
        b = (~0 << highbit) << 1;
        printf("bitMask_(%d,%d) : b = %s\n", highbit, lowbit, bits_uint(binary, b));
    
        c = a ^ b;
        printf("bitMask_(%d,%d) : c = %s\n", highbit, lowbit, bits_uint(binary, c));
    
        d = c >> lowbit;
        printf("bitMask_(%d,%d) : d = %s\n", highbit, lowbit, bits_uint(binary, d));
    
        e = d << lowbit;
        printf("bitMask_(%d,%d) : e = %s\n", highbit, lowbit, bits_uint(binary, e));
    
        return e;
    }
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SDLKey to ASCII without unicode support?
    By zacs7 in forum Game Programming
    Replies: 6
    Last Post: 10-07-2007, 04:03 AM
  2. Help counting number of bits set in an integer
    By JayDiddums10 in forum C Programming
    Replies: 5
    Last Post: 12-07-2006, 03:21 PM
  3. Dealing with bits
    By ILoveVectors in forum C++ Programming
    Replies: 2
    Last Post: 07-02-2005, 08:02 PM
  4. Writing binary data to a file (bits).
    By OOPboredom in forum C Programming
    Replies: 2
    Last Post: 04-05-2004, 04:53 PM
  5. New idea on conveting byte to bits/bits to byte
    By megablue in forum C Programming
    Replies: 10
    Last Post: 10-26-2003, 01:16 AM

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