Like Tree4Likes
  • 1 Post By anduril462
  • 3 Post By Salem

Shift all '1' bits in a number to the left end

This is a discussion on Shift all '1' bits in a number to the left end within the C Programming forums, part of the General Programming Boards category; Hello, I'm working on Practical C Programming exercise 11-6 and have a solution. I just feel like it's kind of ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13

    Shift all '1' bits in a number to the left end

    Hello,

    I'm working on Practical C Programming exercise 11-6 and have a solution. I just feel like it's kind of messy, so I wanted to see if others had feedback on a cleaner, easier way. Mind you, we haven't reach pointers yet in the book. Thanks!

    Code:
    /*************************************************************
    	pcp11_6	--	Takes the 1 bits in a number and shifts them to the left
    				end.
    
    *************************************************************/
    #include <stdio.h>
    
    char			line[100];		/* user input */
    unsigned char 	num;			/* number from user input (8-bit)*/
    int			ones_count;	/* number of 1s to shift */
    unsigned char	new_num;		/* new number with shifted bits */
    int			i,j;		        /* counters */
    int			k;		        /* bit shift counter */
    
    int main(void)
    {
    	//initialize vars
    	ones_count = 0;
    	k = 7;
    
    	// Get user input and store in integer
    	printf("Please enter a number (1 to 255): ");
    	fgets(line, sizeof(line), stdin);
    	sscanf(line, "%d", &num);
    
    	// Count number of 1s in the 8-bit number
    	for(i = 0x80; i > 0; i = (i >> 1))
    	{
    		if(num & i)
    		{
    			++ones_count;
    		}
    	}
    
         // Create new number, bit-by-bit
    	for(i = 0x80; i > 0; i = (i >> 1))
    	{
                   // Push all of the 1s to the left side of the new number
    		while(ones_count != 0)
    		{
    			new_num |= 1 << k;
    			i = i >> 1;
    			--ones_count;
    			--k;
    		}
                   // Fill in the rest of the number with 0s
    		new_num |= 0 << k;
    		--k;
    	}
    	printf("\nNew number is = %d.\n", new_num);
    
    	return 0;
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    A couple things first:
    1. Don't use global variables. There's no need here, so move them in to main.
    2. scanf expects a pointer to an int for %d. You give it &num which is a pointer to an unsigned char. This is problematic, since scanf writes 4 bytes of data into a 1 byte spot. Try
    Code:
    unsigned char num;
    int input;
    scanf("%d", &input);
    num = (unsigned char)(input & 0xFF);
    As for a simpler method, the << operator is guaranteed to zero-fill the right bits when you shift, so you don't need to do that yourself. Given that fact, it seems like it would easiest to implement the following pseudo code:
    Code:
    while leftmost bit of num is a zero
        shift num left by 1
    beatbox32 likes this.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Not sure i understand the requirement: what if there are 0s between 1s. Do you want to squeeze out 0s and gather all 1s and cluster them on the left hand side and then right pad the no. with 0s?

  4. #4
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13
    @anduril462

    Thanks for the excellent tips! The Practical C Programming book (at least at this point) uses global variables quite a bit, so it's nice to see a different perspective.

    @itCbitC

    Sorry for the confusion. Here is the exact requirement:

    "Write a program that will take the bits in a number and shift them to the left end. For example, 01010110 (binary) would become 11110000(binary)."

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    A book that encourages unnecessary use of globals just might make me think book burning isn't such a bad idea . You will probably want to throw that out and try something from our book recommendations thread.

    And since you need to squeeze zeros out of the middle, I would try something like:
    Code:
    initialize new_num to 0
    for each bit in num
        if that bit is a 1
            shift new_num right one position and make the leftmost bit a 1
    That will get you through in one loop instead of two.

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,488
    So having counted how many 1's there are, the answer is known without bothering to do any shifting of individual bits.

    (~0) << (8-ones_count)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    One of the many techniques to count the number of bits in a byte involves creating a lookup table for the number of bits in each possible nibble value, then checking the two nibbles in the byte.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13
    *facepalm* Wow, awesome! I didn't think of that Salem... Thanks again guys!

  9. #9
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    I don't think you need a nested for and while loop to create the new number. Just one loop.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    And one of the other techniques for bit counting is to only loop as many times as there are bits set and unset them one at a time:
    Code:
    int ones_count;
    for (ones_count = 0; num; ones_count++)
      num &= num - 1;
    new_num = ~0 << (8-ones_count);
    Last edited by iMalc; 07-06-2011 at 01:23 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Code:
    int input;   // user input
    int test = 128;  // one bit set
    int bits = 0;
    
    while(test > 0)
      { if (input & test)
          bits++;
        test /= 2; }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Left shift a string
    By Tigers! in forum C Programming
    Replies: 10
    Last Post: 08-16-2009, 11:58 PM
  2. Left Shift elements of a 2D array
    By w2look in forum C Programming
    Replies: 8
    Last Post: 01-22-2009, 11:13 PM
  3. Left Shift
    By vb.bajpai in forum C Programming
    Replies: 4
    Last Post: 06-17-2007, 11:15 AM
  4. left shift operator!!!!
    By theblackhat in forum C Programming
    Replies: 2
    Last Post: 10-02-2004, 02:07 AM
  5. Left Shift problem
    By Mox in forum C++ Programming
    Replies: 7
    Last Post: 10-13-2001, 03:58 AM

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