Thread: How to convert to left justified bits?

What would be the best solution to convert to left justified bits within a word?
Let´s say I have a 12bit full value in a short like this:

00001111 11111111

it would be converted into:

11111111 11110000

I have been trying different bitwise operations but haven´t come up with one that always works regardless of value.

Well, you have to decide what you mean by "left justified". Do you mean you want the first bit to be a one, no matter what, or do you want your smaller-than-sixteen-bit-sized-thing to live at the left rather than the right?

If the latter, then you would shift 16-size; if the former, you would shift until your number goes negative (assuming you're dealing with a signed datatype) or bigger than 2^(n-1) (if not).

Originally Posted by Subsonics

I have been trying different bitwise operations but haven´t come up with one that always works regardless of value.

shift left by one until the left most bit is set.

Code:

unsigned short left_justify(unsigned short x)
{
    while ((x & 0x8000) == 0) x <<= 1;
    return x;
}

Originally Posted by tabstop

Well, you have to decide what you mean by "left justified".

he did decide, and explained it perfectly too. you're just overcomplicating things.

Originally Posted by tabstop

, or do you want your smaller-than-sixteen-bit-sized-thing to live at the left rather than the right?

Yes, that´s what I´m after, any unused bits should be on the right side.

Originally Posted by tabstop

If the latter, then you would shift 16-size;

Ok, that seems solid but how do I get the bit size?

A humble question:

What could this be good for?

an easy answer:

don't bother because you can almost always get better results optimizing other things.

How can you solve this in constant time? ;-)

do a BSR (bit scan reverse), and shift left by this amount (assuming BSR is constant time).

Or, in the case of 16-bits, a BSR table can be constructed.

I´m going to use it for de-coding linear pcm audio data to SDS in preparation for sending it over midi. According to the spec (which is from 86 and sparse), the MSB should be padded and all bits be left justified. I might have misunderstood the docs though because I can´t grasp how the recieving end could interpret a 1 from say 16.

This is what the doc I found says about it:

"The packet number is followed by 120 bytes of data, which form
60, 40, or 30 words (MSB first for multiword samples), depending on
the length of a single data sample.
Each data byte hold seven bits, with the msb in each byte set to
0, in order to conform to the requirements of MIDI data transmission.
Information is left justified within the 7-bit bytes, and unused bits
are filled with 0.
Example: Assume a data point in the memory of a 16-bit sampler,
with the value 87E5. In binary, that would be

1000 0111 1110 0101

and would be encoded as the following MIDI data stream:

01000011 01111001 00100000"

The problem here is that the example is a full 16 bit value, I´m not exactly sure what happens with smaller values right now.

yeah, __builtin_clz() is probably a better idea, in terms of portability (to different architectures, but still using GCC). GCC will use whatever equivalent instruction the CPU has to implement that function, and provide a software implementation if there is none. That's usually what we want.

Originally Posted by Meldreth

shift left by one until the left most bit is set.

Code:

unsigned short left_justify(unsigned short x)
{
    while ((x & 0x8000) == 0) x <<= 1;
    return x;
}

he did decide, and explained it perfectly too. you're just overcomplicating things.

Given the example below, where the left-most bit is not always set, I'd say that the question seems justified.

Anyway, based on what I'm reading from your specs, either you have 16-bit, 24-bit, or 32-bit sampling and those are your choices. I don't know whether you can try to cram smaller things in there; that depends on whether the program that's reading from the other side would know what to do with it.