Fog Creek Software
Discussion Board




Byte shift

As a certified noob, I never quite understood the byte shift scene. What is a byte shift? Why do you do it? Why do you want to do it? Where and how do you use it, in real life?

Any charitable soul who helps me, shall be deemed a saint.

noob
Monday, June 21, 2004

Is it byte shift or bit shift?

MyNameIsSecret();
Monday, June 21, 2004

Thanks for confusing me a bit further. I needed that.

noob
Monday, June 21, 2004

You are really a noob arent you. A byte is eight bits. A bit is either one or zero. All numbers in the computer are formed from bits. So a byte can represent any number from 0 to 255. Still confused?

MyNameIsSecret();
Monday, June 21, 2004

Where does the shift part enter?

noob
Monday, June 21, 2004

when you bit shift you just move the bits right or left. When you move the bits around due to the construction of the binary it is the same as you would divide or multiply with two. It is alot faster to move the bits around than you would actually do calculation. Usages for this are usually when you like to fiddle with the bits. The most I used it for was to reorder bytes from differents types of computers(little-endian to big-endian).

MyNameIsSecret();
Monday, June 21, 2004

To make the confusion worse (-8  : an octet is 8 bits. A byte is usually 8 bits, bit it can also be 6, 7, or 9 nine bits, this being machine-dependant.

Karel Thönissen (www.hello.nl)
Monday, June 21, 2004

Karel, that is not nice. LOL.

MyNameIsSecret();
Monday, June 21, 2004

The shift part is e.g. for when you need to access parts of bytes (or words), or to assemble a word from different parts.

Let's take RGB color values for example: they are often stored as a number consisting of four bytes as follows: 0x00bbggrr. To assemble the color out if its components, you can use the RGB() macro which uses shifts:

#define RGB(r, g ,b)  ((DWORD) (((BYTE) (r) | ((WORD) (g) << 8)) | (((DWORD) (BYTE) (b)) << 16)))

In other words, you
- take the red value as is
- shift the green value left 8 bits, so it occupies the second least significant byte
- shift the blue value left 16 bits
- OR it al together

In the other direction, you have e.g. GetGValue to get the green value:

#define GetGValue(rgb)  ((BYTE) (((WORD) (rgb)) >> 8))

Shift right 8 bits so the value comes in the least significant byte, and cast to BYTE to get rid of whatever is still present in the other bytes.

vrt3
Monday, June 21, 2004

I would think that last message confused him alot. :)

MyNameIsSecret();
Monday, June 21, 2004

You have no idea of how much.... :)

Come on, some simple, down to earth examples.

noob
Monday, June 21, 2004

Noob: the example is correct you just need to get down to earth with the binary in it. http://en.wikipedia.org/wiki/Binary_numeral_system is good reading.

MyNameIsSecret();
Monday, June 21, 2004

And also http://en.wikipedia.org/wiki/Bitwise_operation
it has a header called bit shift.

MyNameIsSecret();
Monday, June 21, 2004

what about a nite shift?

   
Monday, June 21, 2004

noob,

Shift are really simple, you've been doing them since your earliest schooling.  Think of the following sums:

What is 1234 * 100?

What is 9840 / 10?

Any kid can tell you that to multiply by 100 you just add two zeros.  In other words move the digits to the left twice, filling the empty spaces with zeros.  In other words shift twice to the left.  Giving 123400.

To divide by 10 you shift right once.  Giving 984.

Internally, computers count in 1s and 0s: Binary.  Since you are dealing with base 2 then multiplying by 2 has the same effect as multiplying by 10 in deimal.

for example the binary for 6 is 110.  6 x 2 is 12.  The binary for 12 is 1100.  110 shifted left once is 1100.  12 / 2 = 6.  1100 shifted right once is 110.

So the main reason for having shift operations is for having a quick shortcut to multiplication and division operations.

Since then programmers have found lots of other uses for them, as you can see from the RGB example above.

Ged Byrne
Monday, June 21, 2004

Dear S9C12

Why?  Why? Why?

Figure it out yourself.

Quit spending so much time in your CyberCafe.

Please sign your name on all the software you write.  This way I wont use it.

anon
Monday, June 21, 2004

Wrong thread?

noob
Monday, June 21, 2004

SC912??????

Ged Byrne
Monday, June 21, 2004


Just to clear things up, I haven't made this post. Clearly, someone is after my life and in that they are trying to make it look like I am posting in other posters' names (see the MarkTaw threads). The threads there suggested I did those posts by talking about rediffmail. I hold a rediffmail account and so the poster thought he'd frame me by hinting it was me posting in disguise. Two mistakes he made were:

(1) The wrong punctuation. Notice sentences like -

Nice haircut Sathyaish!

which should've been: Nice haircut, Sathyaish.

And a similarity in the sentence (from one of the MarkTaw posts)-

Why did you post as MarkTaw Sathyaish?

(2) It isn't Redif Mail. It's rediffmail, with a double f.

I don't do that. I would never do that. Looks like someone needs medication.

Good bye, JoS!

Sathyaish Chakravarthy
Monday, June 21, 2004

Sathyaish Chakravarthy:
I don't know why you decided to say that here, but this post is definitely not a troll.

On the other hand, "you" posting here could be a troll. Ah, JoS posters are starting to develop really nice personalitys...

noob
Monday, June 21, 2004


This is why:

Here's what I posted!
http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=154147&ixReplies=10

Here's what I did NOT post but someone has been trying to make it like I posted them:

(1) http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=154013&ixReplies=2

What the impostor missed out was the signature that Philo uses at the end of his posts.

(2) http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=154179&ixReplies=25

(3) http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=154204&ixReplies=16

(4) http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=154371&ixReplies=4

Sathyaish Chakravarthy
Monday, June 21, 2004

I think we're facing the most intelligent spambot devised by Man.

noob
Monday, June 21, 2004

>> "Good bye, JoS!"

L4t3r l33t c0d3r dewd!

anon
Monday, June 21, 2004

What fun!  Posts all over the place.

Bit Shifting: 
1.  Most processors have special instructions for simply shifting the bits of a byte/word/longword left or right.  If you shift left, you are multiplying by 2 for each position shifted.  If you shift right, you are dividing by 2 for each position shifted -- and bits shifted off the 'end' of the byte are dropped on the floor.

Since it is a single machine instruction, it can happen very fast.  If you used a 'multiply' instruction, much more code would execute to get the same effect.

2.  An 'octet' is an 8-bit byte -- but since most computers people use (PC's, Suns, Apples) use an 8-bit byte, you can safely assume a 'byte' is 8-bits. YMMV.

3.  The 'C' symbol for a right-shift is '>>'.  Left-shift is '<<'.

AllanL5
Monday, June 21, 2004

On the internet nobody knows you are a dog.

*woof*
Monday, June 21, 2004

You forgot to explain the difference between arithmetic and logical shift.

Oink

piggy
Monday, June 21, 2004

So, this whole shebang gets even funnier, right?

noob
Monday, June 21, 2004

No it doesn't. At least I hope so.

MyNameIsSecret();
Monday, June 21, 2004

Some more confusion: there are two kinds of shifts, namely logical shifts and arithmetic shifts.

The difference is in right shifts: with logical shifts, 0-bits are shifted in: 10101010b >> 1 = 01010101b

With arithmetic shifts, it depends on the most significant bit. When 0, the new most significant bit is also a 0. When 1, the new most significant bit is also a 1.

10101010b >> 1 = 11010101b
01010101b >> 1 = 00101010b

Using this method of arithmetic shifts, the method can also be used for division of negative numbers by 2, 4, 8 etc. At least if two's complement ( http://en.wikipedia.org/wiki/Two's_complement ) is used for negative numbers, but I think that's the only format used nowadays for integers.

For example:
10 decimal is 00001010 binary
To calculate the binary representation of -10, first inverse all bits: 11110101
Then add 1 to that: 11110110
So: -10 decimal = 11110101 binary

Arithmetic right shift: 11110101 >> 1 = 11111011
Invert: 00000100
Add one: 00000101
00000101 binary equals 5 decimal, so
11111011 binary equals -5 decimal, which happens to be -10/2

vrt3
Monday, June 21, 2004

Isn't a byte always 8 bits, since Byte is a rather dyslexic abbreviation of By Eight?  I was taught that anything else is a 'word.'

Ged Byrne
Monday, June 21, 2004

Oh my god. noob feels claustrofobia setting in.

noob
Monday, June 21, 2004

Back in the mists of time I was taught that a nibble was four bits.  I suspect this doesn't help anyone.

a cynic writes...
Monday, June 21, 2004

Sometimes I nibble on my girlfriend. It helps a lot.

noob
Monday, June 21, 2004

Noob, is it for a school/college class or is it for your personal curiosity?

MyNameIsSecret();
Monday, June 21, 2004

OK, noob if YOU'RE not going to be serious about this, I think there is no hope.  Sigh.

AllanL5
Monday, June 21, 2004

Not for school. I'm just trying to educate myself.

noob
Monday, June 21, 2004

The remark about the nibble was just a small joke. Please don't take it seriously. I see no use in making fun of the people who help me. I know better.

noob
Monday, June 21, 2004

Noob, Well, then I suggest you start experimenting with binary computation. The stuff becomes much clearer when you realize how the binary stuff works!

MyNameIsSecret();
Monday, June 21, 2004

noob, you might want to check out this illustrated explanation:
  http://webster.cs.ucr.edu/AoA/Windows/HTML/DataRepresentationa6.html

If it doesn't make sense right away, I'd suggest backing up a few sections and start with the review of binary representations, bits/bytes/words, etc.

John C.
Monday, June 21, 2004

Shifting left and right is actually very simple. Even political candidates know how to do it.

Oink

piggy
Monday, June 21, 2004

I think you'll find its nybble.

ICL called their 6bit words, bytes.

Simon Lucy
Monday, June 21, 2004

Byte is not a contraction of By Eight. It is a pun on the word bite, based on the idea that a byte is a bite-sized chunk of memory that is easy to deal with. Really.

Remember that computer people always had a wicked sense of humour, derived from the fact that in the beginning computers were the most wonderful toys known to man.

These days, computers are the most significant source of stress, high blood pressure and aggravation known to man. Oh well...

Ian
Monday, June 21, 2004

Many people in this thread have been making the mistake of treating a bit pattern as the same thing as a binary number.

This is not a good way to think. A bit pattern can be interpreted (in more than one way) as a number, but really a bit pattern is just a string of bits.

This confusion could be eliminated by writing

01011101

as

.X.XXX.X

This avoids the semantic overload inherent in using numerical digits to represent the set and unset states of bits.

For an example of why we should do this, ask yourself what number this bit string

XX.....X ..X..... ........ ........

represents?

Once we manage to stop thinking "numbers" all the time, the bit shift operators become much easier to understand as just shifting bit strings to the left or right.

Bit shifting as multiplying and dividing by powers of 2 is an interpretation that is sometimes correct, but not always, and only when you really understand what is going on with the representation.

Ian
Monday, June 21, 2004

Many people in this thread think that Ian is dumb.

piggy
Monday, June 21, 2004

noob, good question imho. I rarely as in NEVER use such bitshifters cus I never work at the bit level but I know Perl has bitwise although I never used it ... interesting stuff. Can we use any of this in scripting languages? I wonder.

me
Monday, June 21, 2004

I have always found bit operations very confusing
as well. It might help to understand what they
are used for.

1. Microprocessors have direct instructions for manipulating
bits so those operations are very fast. This encourages people to encode information as 0s or 1s in particular places in bytes. The bit operations allow you to get and set  information as bits in bytes.
2. You can encode large amounts of information in bits very efficiently from a space point of view. 
3. Computers communicate with attached hardware using registers which encode information as bits. So when dealing with hardare there's a lot of use of bits.

son of parnas
Monday, June 21, 2004

Ian, being a noob he gets the simplified version. There is no point in confusing him with the finer points of arithmetic and logic shifting.

MyNameIsSecret();
Monday, June 21, 2004

Really? I thought Ian's was unusually good. Esp for beginners. I didn't read the entire thread though.

Tayssir John Gabbour
Monday, June 21, 2004

This could go on forever.

Yes, "bytes" were (are) predominantly 8-bit units of storage or operating register space.  Many other units have been used however, 6-bit units having been fairly common in the early days.

Don't confuse "byte" and "character" however.  CDC 6000 series machines and their immediate successors for example typically used 6-bit characters.  At the same time they employed peripheral processors that used a 12-bit word often referred to as a "byte."  Since typical programmers never "saw" these PPs it had little impact on the general culture in such shops.  Decimal machines (yes, there were many commercial machines that were wired or microprogrammed to look "decimal" to a programmer) had other creative ways of representing characters - often as two decimal digits.  Then we have Unicode and other 16-bit "character sets" floating around.

For all intents and purposes today, "byte" is used to refer to 8-bit units.

"Nibbles" were always 4-bit units in my experience, perhaps others encountered other usages.  "Nybble" however was merely an illiterism that seemed to gain some strength among hobbyists of the 1970s.  It is seldom seen any longer except among the radically contrary among us.

Arithmetic shifting is basically a means of doing fast integer multiplication or division by powers of two.  Logical shifting is the same thing, less the sign-extension complexity already described.

It is hard to imagine a shifting discussion without venturing into masking, which involves performing bit-wise boolean operations on some addressable, manipulable set of bits.

Those CDC 6000 machines for example had a 60-bit single-precision word.  Through most of their service life they employed a proprietary 6-bit character set.  This gave 64 symbols - basically no lowercase letters, but often the value 00 (octal, hex was not used much during this era) was reserved, leaving you 63 characters.

This example is interesting because the CPU had no instructions for addressing any unit of storage less than a 60-bit word as data.  So how did something like a compiler (or any random user program) process individual characters as text?  Why, through shifting and masking operations to isolate the desired character into the lower 6 bits of a word (or upper, or whatever tickled your fancy really, more often the low-order bits were used though).  Similar techniques were used to insert (pack) a character back into a word.

Extrapolating this technique to other bit-field sizes (whether one, two, three, or 14 bits) shows why shifting and masking can still be important today.  Bit and di-bit vectors are used all over the place.

Shifting and masking are also used for computational optimization and extended-precision arithmetic.  Encryption/decryption is an example of a computationally intensive real-world task today, and one where such techniques are valuable.  Codecs for audio and other analog peripherals also involve a good deal of bit-fiddling.

As for the world being all two's complement, t'ain't so.  There is plenty of one's complement around, and even multi million dollar mainframes being purchased that used the signed-magnitude approach to number representation.

Never forget that the Intel i386 and compatible neighborhood is just one small (though crowded) ghetto.  Other parts of "town" may not be as populous, but it doesn't mean they don't exist or that they don't make valid contributions to the culture and ecosystem.

Bob Riemersma
Monday, June 21, 2004

OK I think I understand shifting left and right now. but how do you shift bits up and down?

noob
Monday, June 21, 2004

For up and down shifting you need to move your
head up and down.

son of parnas
Monday, June 21, 2004

That wasn't me posting. I can't believe someone's stealing my secret identity!

noob
Tuesday, June 22, 2004

*  Recent Topics

*  Fog Creek Home