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

[beatbox32]

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!

/*************************************************************
	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;
}

[anduril462]

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

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:

while leftmost bit of num is a zero
    shift num left by 1

[itCbitC]

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?

[beatbox32]

@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)."

[anduril462]

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:

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.

[Salem]

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)

[laserlight]

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.

[beatbox32]

*facepalm* Wow, awesome! I didn't think of that Salem... Thanks again guys!

[nonoob]

I don't think you need a nested for and while loop to create the new number. Just one loop.

[iMalc]

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:

int ones_count;
for (ones_count = 0; num; ones_count++)
  num &= num - 1;
new_num = ~0 << (8-ones_count);

[CommonTater]

int input;   // user input
int test = 128;  // one bit set
int bits = 0;

while(test > 0)
  { if (input & test)
      bits++;
    test /= 2; }