Thread: Several misc. C questions

I'm teaching myself C at the moment, and I want to ask a few questions that are puzzling me at the moment.

First, I'm working with bitwise operators at the moment, trying to familiarize myself with their use. I understand WHAT all the different operators I've been exposed to( & , |, ^, ~, and <</>>) are supposed to do, but some of the exact details are a bit fuzzy.

I was looking at the solution posted to problem 2-7 in K&R:

Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.

The page I browed had this solution:

Code:

unsigned invert(unsigned x, int p, int n)
{
    return x ^ (~(~0U << n) << p);
}

/* main driver added, in a hurry while tired, by RJH. Better test driver suggestions are welcomed! */

#include <stdio.h>

int main(void)
{
  unsigned x;
  int p, n;

  for(x = 0; x < 700; x += 49)
    for(n = 1; n < 8; n++)
      for(p = 1; p < 8; p++)
        printf("%u, %d, %d: %u\n", x, n, p, invert(x, n, p));
  return 0;
}

I noticed a couple bugs in the code, so I modified it a bit, including renaming all the variables, because, while brevity is great, I WILL get mixed up while reading code if the variable names aren't clear:

Code:

#include <stdio.h>

/* Modified version of solution to exercise 2-7. Original by RJH. */

unsigned int flipbits(unsigned int opvar, int flipnum, int flipadr)
{
return opvar ^ (~(~0U << flipnum) << (flipadr-flipnum));
}

int main(void)
{
unsigned int opvar;
int flipnum, flipadr;

for(opvar = 0; opvar < 700; opvar += 49)
	for(flipnum = 1; flipnum < 8; flipnum++)
		for(flipadr = flipnum; flipadr <= 8; flipadr++)
			printf("%u, %d, %d: %u\n", opvar, flipnum, flipadr, flipbits(opvar, flipnum, flipadr));
return 0;
}

My understanding in making the modifications is that the offset should not be exceeded by the number of bits to be flipped, and that the mask created by(in the original code)

Code:

(~(~0U << n) << p)

would end up placed by the original code so that its leftmost bit was at bit n+p+1, whereas it should be placed at p+1.

Is this a correct assessment?

Also, I want to make sure I understand exactly what this(updated) code is doing:

1. Generate a single bit 0 with 0U, then reverse it to single bit 1U

2. Move 1U flipnum places to the left, resulting in(where flipnum == 5) 100000

3. Reverse 100000 to 011111

4. Move 011111 (where offset == 7) an additional 2 places left, to make 01111100

5. Apply this mask to opvar, flipping all bits that line up with the 1s, then return this numeric value as an int.

I was considering that in the main function, could not

Code:

    for(flipnum = 1; flipnum < 8; flipnum++)
      for(flipadr = flipnum; flipadr <= 8; flipadr++)

be replaced with

Code:

    for(flipnum = 1; flipnum < sizeof(int); flipnum++)
      for(flipadr = flipnum; flipadr <= sizeof(int); flipadr++)

to more strenuously test the function? I mean, not that it really *needs* the testing, but just in theory. Also, if you were using more dynamic values, I'd think that checking for flipnum > flipadr would be a good idea inside the function, since that could have unexpected results.

Also, a question about pointers:

I am guessing from what I've read that local variables aren't illegal to write to by other functions, just not visible. In other words, if function a() calls function b(), and passes a local variable address to it, that function b() would be able to alter the contents of that variable, since it now knows where it is.

EG., in scanf(), you pass it the address of some variable, it writes data to that address, then ends.

Is this a correct understanding, or am I completely off track?

Thanks for anyone's help in advance, hope I'm not being a nuisance.

Edit: Fixed some stupid typos.

In other words, if function a() calls function b(), and passes a local variable address to it, that function b() would be able to alter the contents of that variable, since it now knows where it is.

correct. This simple example elaborates the concept :

Code:

#include <stdio.h>

void foo(int *pointer)
{
	*pointer = 5; /* modifies the value of LocalVariable */
}

int main(void)
{
	int LocalVariable = 10;

	printf("LocalVariable before calling 'foo' : %d\n", LocalVariable);

	foo(&LocalVariable); /* sending the adress-of (&) LocalVariable */

	printf("LocalVariable after calling 'foo' : %d\n", LocalVariable);

	return 0;
}

hope this helps

I am guessing from what I've read that local variables aren't illegal to write to by other functions, just not visible. In other words, if function a() calls function b(), and passes a local variable address to it, that function b() would be able to alter the contents of that variable, since it now knows where it is.

EG., in scanf(), you pass it the address of some variable, it writes data to that address, then ends.

That's correct. The iffy part is your statement local variables aren't illegal to write to by other functions. This is only true if the local variable still exists. A lof of people get into trouble with code like this:

Code:

char *foo(void)
{
  char buf[10];

  strcpy(buf, "foo");
  return buf;
}

int main(void)
{
  printf("%s\n", foo());
  return 0;
}

Local variables are created on the stack. So it's okay for function a() to call function b() and pass the address of a local variable to it, then have b() use that variable that was passed to it. But it's not okay to have function a() call function b() which returns the address of a local variable back to a() and have a() use that variable.

I'm going to have a go at the bit inversion code after I look at it

Yeah, I realized that while I was typing the question about pointers; I ran through my head what would happen if a pointer to a local variable in the called function was returned, and surmised that the results would be less than consistant.

Edit:
I assume, though, that if a() called b(), b() could return a pointer to a local, static variable without mishap.

Originally Posted by Aerie

I was looking at the solution posted to problem 2-7 in K&R:

Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.

The page I browed had this solution:

<snip>

I noticed a couple bugs in the code, so I modified it a bit

The solution posted there correctly answers the question, yours does not. Note the differences between this

Code:

0, 1, 1: 00000000000000000000000000000010
0, 1, 2: 00000000000000000000000000000110
0, 1, 3: 00000000000000000000000000001110
0, 1, 4: 00000000000000000000000000011110
0, 1, 5: 00000000000000000000000000111110
0, 1, 6: 00000000000000000000000001111110
0, 1, 7: 00000000000000000000000011111110
0, 2, 1: 00000000000000000000000000000100
0, 2, 2: 00000000000000000000000000001100
0, 2, 3: 00000000000000000000000000011100
0, 2, 4: 00000000000000000000000000111100
0, 2, 5: 00000000000000000000000001111100
0, 2, 6: 00000000000000000000000011111100

and this

Code:

0, 1, 1: 00000000000000000000000000000001
0, 1, 2: 00000000000000000000000000000010
0, 1, 3: 00000000000000000000000000000100
0, 1, 4: 00000000000000000000000000001000
0, 1, 5: 00000000000000000000000000010000
0, 1, 6: 00000000000000000000000000100000
0, 1, 7: 00000000000000000000000001000000
0, 1, 8: 00000000000000000000000010000000
0, 2, 2: 00000000000000000000000000000011
0, 2, 3: 00000000000000000000000000000110
0, 2, 4: 00000000000000000000000000001100
0, 2, 5: 00000000000000000000000000011000
0, 2, 6: 00000000000000000000000000110000
0, 2, 7: 00000000000000000000000001100000
0, 2, 8: 00000000000000000000000011000000

in regard to the original question. For example, the highlighted line doesn't look like the value 0 with the 6 bits beginning at bit 2 inverted.

1. Generate a single bit 0 with 0U, then reverse it to single bit 1U

Code:

~0U

This means all value bits of an unsigned int set to 1; which is UINT_MAX.

[edit]Here's what's going on:

Code:

#include <stdio.h>

void showbits(unsigned int byte)
{
   unsigned int bit;
   for ( bit = (~0U >> 1) + 1; bit; bit >>= 1 )
   {
      putchar(byte & bit ? '1' : '0');
   }
   putchar('\n');
}

unsigned invert(unsigned x, int p, int n)
{
   unsigned temp;
   printf("x = %u, p = %d, n = %d\n", x, p, n);
   temp = 0U;        fputs("        0U:             ", stdout); showbits(temp);
   temp = ~temp;     fputs("       ~0U:             ", stdout); showbits(temp);
   temp = temp << n; fputs("       ~0U << n:        ", stdout); showbits(temp);
   temp = ~temp;     fputs("     ~(~0U << n):       ", stdout); showbits(temp);
   temp = temp << p; fputs("     ~(~0U << n) << p:  ", stdout); showbits(temp);
                     fputs("x                     : ", stdout); showbits(x);
   temp = temp ^ x;  fputs("x ^ (~(~0U << n) << p): ", stdout); showbits(temp);
   return x ^ (~(~0U << n) << p);
}

int main(void)
{
   invert(100, 6, 2);
   return 0;
}

/* my output
x = 100, p = 6, n = 2
        0U:             00000000000000000000000000000000
       ~0U:             11111111111111111111111111111111
       ~0U << n:        11111111111111111111111111111100
     ~(~0U << n):       00000000000000000000000000000011
     ~(~0U << n) << p:  00000000000000000000000011000000
x                     : 00000000000000000000000001100100
x ^ (~(~0U << n) << p): 00000000000000000000000010100100
*/

I assume, though, that if a() called b(), b() could return a pointer to a local, static variable without mishap.

Correct!

Waitasec....

Okay, I had a big long post written out, but I realized I was visualizing the bits wrong, thanks to a very poor explanation I read a while back.

Basically, I was counting the bits and offsets in reverse from how I should have been, which was throwing all my assumptions off completely.

[edit]Before your edit, you had:

Code:

unsigned int flipbits(unsigned int opvar, int flipnum, int flipadr)
{
   return opvar ^ (~(~0U << flipnum) << (flipadr-flipnum));
}

[/edit]

Code:

x = 100, p = 6, n = 2
100:      00000000000000000000000001100100
invert:   00000000000000000000000010100100
flipbits: 11110000000000000000000001100100

Great, your post confirms what I thought, which means I have to completely rebuild the way I was thinking about bit offsets. Bleah.

Oh well, thanks for explaining this.

Edit: I was basically counting to the right when applying the mask, instead of to the left. So a mask "at" bit 2 would have its leftmost bit at bit 2, instead of its rightmost.

If you operate making that assumption, my code works perfectly.

Another pointer question:

I know pointers can be incrimented, but I want to ask, when you point a void pointer at an element in an array, then incriment that pointer, does the pointer always automagically know how 'far' in memory to advance to point to the beginning of(as opposed to the middle of) the next element in the array?

Arithmetic can't be performed on pointers to void because there's no size information for a generic pointer. If, on the other hand, you use a pointer to T where T is the type of the array, then when you increment the pointer, it moves sizeof(T) bytes so that everything "just works".

What do you mean, 'pointer to T where T is the type of the array'?

Do you mean, instead of void *, doing int * when you want the pointer to point to an int array? I knew already that would work as I described.

Note: I'm getting tired, so pay no mind if I stop making sense. Just let me know so I can take a break.

>Do you mean, instead of void *, doing int * when you want the pointer to point to an int array?
Yes. Using void * won't work though.

Okay. So, what're void pointers used for, that's not replicable with other pointer types?

Pointers to void are used when you don't know what the type of pointer is, or it may change depending on the use. Because pointers to void can be converted to any object pointer implicitly in C, it really does mean "any object pointer type". For example, malloc returns a pointer to void, yet you can still do this:

Code:

int *p = malloc(10 * sizeof(int));
char *q = malloc(50);
void *r = malloc(size);

So while you can't do very much with the void pointer itself, it greatly simplifies generic programming via these effortless conversions.