Printable View
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).
shift left by one until the left most bit is set.Quote:
Originally Posted by Subsonics
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.Quote:
Originally Posted by tabstop
Yes, thatīs what Iīm after, any unused bits should be on the right side.Quote:
Originally Posted by tabstop
Ok, that seems solid but how do I get the bit size?Quote:
Originally Posted by tabstop
Thanks for that Meldreth,Quote:
Originally Posted by Meldreth
A humble question:
What could this be good for?
A tough question:
How can you solve this in constant time? ;-)
an easy answer:
don't bother because you can almost always get better results optimizing other things. ;)
For most practical purposes, you are right: optimizing without profiling is stupid. In addition to that, I was completely mistaken: I know a nice and clever way to get the number of trailing zeros in the binary representation of an integer making use of de Bruijn sequences and exploiting features of Two's Complement representation. I'd be happy to show it here if anyone is interested.Quote:
don't bother because you can almost always get better results optimizing other things.
But unfortunately, the trick doesn't apply to leading zeros. It's still possible to do it in constant time, but it looks quite ugly.
Greets,
Philip
do a BSR (bit scan reverse), and shift left by this amount (assuming BSR is constant time).Quote:
How can you solve this in 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.
Assuming that the machine supports the BSR instruction (x86 since i386 I think), this is right. And as we've already left portability way behind us: gcc has the builtin function __builtin_clz() which computes the number of leading zeros, too.Quote:
Originally Posted by cyberfish
Kids, don't use that! ;-)
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.
Given the example below, where the left-most bit is not always set, I'd say that the question seems justified.Quote:
Originally Posted by Meldreth
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.
Having thought this over I think that what is refered to as unused bits would be to the right of 1 only, otherwise I canīt understand how the data could be understood by the recieving end. In this case the value 1 would be encoded as: 00000000 00000000 00100000 (16bit). I have discussed this earlier here perhaps the older solution was the correct one. That involved copying the short to a byte array and performing right shifts to spread out the data over three bytes.
Based on the specs, I would agree with you. I don't know that you have to use a byte array for the original data really; masking would seem to be the way to go. (Although a byte array for the output would work.)Quote:
Originally Posted by Subsonics
I think my confusion came from that I wanīt to encode 12bit samples. Right now I can only assume that itīs encoded just like 16bit but with the highest legal sample value being 4095. I guess that I will have to try and see. :-) I donīt remember exactly how I ended up solving it the last time but, I think masking was used to get the value of the last byte with the the 2 least significant bits.
If it happens to be encoded into two bytes I think I could use something like this:
Where 00001111 11111111 will become 01111111 01111100
Code:UInt16 sample = 0xfff;
UInt8 outputBuf[2];
sample <<= 3;
memcpy(&outputBuf[0], &sample, 2);
outputBuf[0] >>= 1;
Subsonics, based on the spec for MIDI you posted, it looks like you can't just shift 16-bits... Instead you need to split up into groups of 7 bits because the spec calls for the high bit to be zero in each byte. Only 7 bits are used. So not only shifting the data left but spreading it out some as you cross the byte boundaries.
Iīm not sure what you mean now. In the post above I have done that, the MSB is padded with zero in both bytes. First I shift three bits to the left which leaves me with one leading zero, then I copy the short across two bytes in the output buffer and make a right shift to the last byte. If you refer to the original post then thatīs only one part in solving this that I couldnīt figure out how to do. But I donīt think I will need it now as Iīm pretty sure that the left justifying that is mentioned in the doc only is relevant for the least significant byte.Quote:
Originally Posted by nonoob