Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Shifting bits

Reply
Thread Tools

Shifting bits

 
 
arnuld
Guest
Posts: n/a
 
      11-29-2011
Here is another C interview question, what this C program does. I see it
compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
escape character for hexadecimal notation. Section 7.6.3 says << is
shift-op which shifts bits to left. Type of result after shift-op
returns is the converted left operand and result is not an lvalue.

I never really understood how shifting bits works. I mean, how will I
know -1 will return -16 after shifting 4 bits (if you replace %x with
with %d, you get -16). Is it possible to know in advance e.g what
shifting 8 bits to left on 100 will result.

What practical use is made of shifting bits ?


#include <stdio.h>

int main(void)
{
printf("%x\n", -1<<4);

return 0;
}

=============== OUTPUT ====================
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra interview-2.c
/home/arnuld/programs/C $ ./a.out
fffffff0
/home/arnuld/programs/C $






--
arnuld
http://LispMachine.Wordpress.com
 
Reply With Quote
 
 
 
 
Ian Collins
Guest
Posts: n/a
 
      11-29-2011
On 11/29/11 06:02 PM, arnuld wrote:
> Here is another C interview question, what this C program does. I see it
> compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
> escape character for hexadecimal notation.


The term is "format specifier", not escape character. An escape
character is something completely different.

> Section 7.6.3 says<< is
> shift-op which shifts bits to left. Type of result after shift-op
> returns is the converted left operand and result is not an lvalue.
>
> I never really understood how shifting bits works. I mean, how will I
> know -1 will return -16 after shifting 4 bits (if you replace %x with
> with %d, you get -16). Is it possible to know in advance e.g what
> shifting 8 bits to left on 100 will result.


You won't. I believe sifting a signed integer and this the code is
undefined.

> What practical use is made of shifting bits ?


It's very common when you want to extract bits form a longer type, or
assign a value to high order bits. It used to be used in place of
multiplication or division by a power of two (shift instructions were
typically faster).

--
Ian Collins
 
Reply With Quote
 
 
 
 
Malcolm McLean
Guest
Posts: n/a
 
      11-29-2011
On Nov 29, 7:02*am, arnuld <(E-Mail Removed)> wrote:
>
> What practical use is made of shifting bits ?
>

They were used as a cheap divide or multiply by a power of two. It's
the binary equivalent of adding or deleting a nought to muliply by
ten. This is now obsolete on all but the simplest compilers for small
systems.

However shifts are still used if you want to treat a variable as an
array of bits rather than a number. An example is a stream of
compressed data using Huffman codes. No Huffman code may be a prefix
of another Huffman code. By extracting data one bit at a time, you
can build up the code until you come to a leaf, and thus decompress
the data.

Another example is packing 24 bit rgb values into a 32 bit int. That
means that you can pass a 24 bit colour in one argument, which is
often clearer. circle(x, y, r, color) is more convenient than
circle(x, y, r, red, green, blue).



 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      11-29-2011
"arnuld" <(E-Mail Removed)> wrote in message
news:4ed46774$0$295$(E-Mail Removed)...

>Is it possible to know in advance e.g what
> shifting 8 bits to left on 100 will result.


Since they are both constants, then yes. And the result will be 25600
(effectively 100 * 2**.

#include <stdio.h>

int main(void) {
int i;

for (i=0; i<=16; ++i)
printf("%d shifted left %d place%s is %d\n",100,i, i==1?"":"s", 100<<i);
}

Notice each extra shift multiplies by 2.

> What practical use is made of shifting bits ?


Just look for "<<" or ">>" in any large body of code, and see what people
use it for. Sometimes they can be replaced by multiply and divide, but
shifts are usually more to the point, because they use N rather than 2**N.

--
Bartc

 
Reply With Quote
 
88888 Dihedral
Guest
Posts: n/a
 
      11-29-2011
On Tuesday, November 29, 2011 8:04:16 PM UTC+8, Bart wrote:
> "arnuld" <(E-Mail Removed)> wrote in message
> news:4ed46774$0$295$(E-Mail Removed)...
>
> >Is it possible to know in advance e.g what
> > shifting 8 bits to left on 100 will result.

>
> Since they are both constants, then yes. And the result will be 25600
> (effectively 100 * 2**.
>
> #include <stdio.h>
>
> int main(void) {
> int i;
>
> for (i=0; i<=16; ++i)
> printf("%d shifted left %d place%s is %d\n",100,i, i==1?"":"s", 100<<i);
> }
>
> Notice each extra shift multiplies by 2.
>
> > What practical use is made of shifting bits ?

>
> Just look for "<<" or ">>" in any large body of code, and see what people
> use it for. Sometimes they can be replaced by multiply and divide, but
> shifts are usually more to the point, because they use N rather than 2**N.
>
> --
> Bartc


Didn't you ever implement cordic before in C?

That was the homework not difficult in C who had to learn how to write
an assembler and a restricted compiler of some fat standard.
 
Reply With Quote
 
gwowen
Guest
Posts: n/a
 
      11-29-2011
On Nov 29, 5:02*am, arnuld <(E-Mail Removed)> wrote:

> What practical use is made of shifting bits ?


Besides the other answers here - CRC32 and the like are usually
defined/implemented in terms of bitshifts.

Also they're good in the abstract for explaining the concept of
sensitive-dependence-on-initial-conditions.
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      11-29-2011
Ian Collins <(E-Mail Removed)> writes:
<snip>
> [...] I believe sifting a signed integer and this the code is
> undefined.


That's a good shorthand, since it will encourage the use of unsigned
ints wherever possible, but it is not true as you have stated it. 1<<4
is a shift of a signed int and is well-defined. The exact rules can be
found in the C standard (search for n1256.pdf) or in any good C text,
but it's better to forget them! Use unsigned ints for bit operations.

The OP's code:

printf("%x\n", -1<<4);

is probably undefined for two reasons (the other being the technical
detail that %x expects an unsigned int argument) and writing

printf("%x\n", (unsigned)-1<<4);

would have fixed both. Who sets these interview questions?

<snip>
--
Ben.
 
Reply With Quote
 
DDD
Guest
Posts: n/a
 
      11-30-2011
On Nov 29, 1:02*pm, arnuld <(E-Mail Removed)> wrote:
> Here is another C interview question, what this C program does. I see it
> compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
> escape character for hexadecimal notation. Section 7.6.3 says << is
> shift-op which shifts *bits to left. Type of result after shift-op
> returns is the converted left operand and result is not an lvalue.
>
> I never really understood how shifting bits works. I mean, how will I
> know -1 will return -16 after shifting 4 bits (if you replace %x with
> with %d, you get -16). Is it possible to know in advance e.g what
> shifting 8 bits to left on 100 will result.
>
> What practical use is made of shifting bits ?
>

C language is used widely in embedded system. Bit operations are
very common.
> #include <stdio.h>
>
> int main(void)
> {
> * printf("%x\n", -1<<4);
>
> * return 0;
>
> }
>
> =============== OUTPUT ====================
> /home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra interview-2.c
> /home/arnuld/programs/C $ ./a.out
> fffffff0
> /home/arnuld/programs/C $
>
> --
> *arnuldhttp://LispMachine.Wordpress.com


 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      11-30-2011
On 11/29/2011 11:42 PM, DDD wrote:
> On Nov 29, 1:02�pm, arnuld <(E-Mail Removed)> wrote:

....
>> What practical use is made of shifting bits ?
>>

> C language is used widely in embedded system. Bit operations are
> very common.


It would have been more responsive to explain what those bit operations
on embedded systems are actually used for.
--
James Kuyper
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      11-30-2011
> On Tue, 29 Nov 2011 17:39:12 +0000, Ben Bacarisse wrote:

> Ian Collins <(E-Mail Removed)> writes: <snip>
>> [...] I believe sifting a signed integer and this the code is
>> undefined.

>
> That's a good shorthand, since it will encourage the use of unsigned
> ints wherever possible, but it is not true as you have stated it. 1<<4
> is a shift of a signed int and is well-defined. The exact rules can be
> found in the C standard (search for n1256.pdf) or in any good C text,
> but it's better to forget them! Use unsigned ints for bit operations.


I have H&s5 here. Section 7.6.3 states "Applying the shift operator >> is
not portable when the left operand is negative, signed value and the
right operand is nonzero"

What I noticed are two things:

(1) My examlpes uses << rather than >>. Hence above rule does not apply
(2) H&S5 is using word "and" rather than word "or", which directly means
all three conditions in "negative, signed value and right operand is
zero" must be satisfied.


n1256.pdf in Section 6.5.7 (4) states:

"The result of E1 << E2 is E1 left shifted E2 but positions; vacated
bits are filled with zeroes. If E1 has unsigned type, the result is
E1x2^E2, reduced modulo one more than the maximum value representable in
the result type. If E1 has a signed type and nonnegative value, and
E1x2^E2 is representable in the result type, then that is resulting
value; otherwise , the behavior is undefined"

It is proved that this interview code has undefined behavior.
(unfortunately it was a MCQ (Multiple Choice Question) and undefined
behavior was not one of the options).



> The OP's code:
>
> printf("%x\n", -1<<4);
>
> is probably undefined for two reasons (the other being the technical
> detail that %x expects an unsigned int argument) and writing


hey.. I did not know this %x secret



> printf("%x\n", (unsigned)-1<<4);
>
> would have fixed both. Who sets these interview questions?


Yes, that casting fixes as per standard says. Thanks for that. Regarding
interview questions, once I was asked the value of i after this operation:

i = i++;

I said its UB but the guy did not like my answer.




--
arnuld
http://LispMachine.Wordpress.com
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Shifting bits jacob navia C Programming 6 10-28-2009 08:45 AM
Shifting unsigned long long values by 64 bits krunalb C Programming 10 01-23-2007 02:47 PM
shifting bits, shift 32 bits on 32 bit int GGG C++ 10 07-06-2006 06:09 AM
8-Bits vs 12 or 16 bits/pixel; When does more than 8 bits count ? Al Dykes Digital Photography 3 12-29-2003 07:08 PM
win XP 32 bits on a 64 bits processor.. Abbyss Computer Support 3 11-13-2003 12:39 AM



Advertisments