Asked  6 Months ago    Answers:  5   Viewed   30 times

I am trying to figure out how exactly arithmetic bit-shift operators work in C, and how it will affect signed 32-bit integers.

To make things simple, let's say we work within one byte (8 bits):

x = 1101.0101
MSB[ 1101.0101 ]LSB

Reading other posts on Stack Overflow and some websites, I found that: << will shift toward MSB (to the left, in my case), and fill "empty" LSB bits with 0s.

And >> will shift toward LSB (to the right, in my case) and fill "empty" bits with MS bit

So, x = x << 7 will result in moving LSB to MSB, and setting everything to 0s.

1000.0000

Now, let's say I would >> 7, last result. This would result in [0000.0010]? Am I right?

Am I right about my assumptions about shift operators?

I just tested on my machine, **

int x = 1;   //000000000......01

x = x << 31; //100000000......00

x = x >> 31; //111111111......11 (Everything is filled with 1s !!!!!) 

Why?

 Answers

50

Right shift of a negative signed number has implementation-defined behaviour.

If your 8 bits are meant to represent a signed 8 bit value (as you're talking about a "signed 32 bit integer" before switching to 8 bit examples) then you have a negative number. Shifting it right may fill "empty" bits with the original MSB (i.e. perform sign extension) or it may shift in zeroes, depending on platform and/or compiler.

(Implementation-defined behaviour means that the compiler will do something sensible, but in a platform-dependent manner; the compiler documentation is supposed to tell you what.)


A left shift, if the number either starts out negative, or the shift operation would shift a 1 either to or beyond the sign bit, has undefined behaviour (as do most operations on signed values which cause an overflow).

(Undefined behaviour means that anything at all could happen.)


The same operations on unsigned values are well-defined in both cases: the "empty" bits will be filled with 0.

Tuesday, June 1, 2021
 
antoniputra
answered 6 Months ago
52

Bit interleaving essentially takes two n bit input numbers and produces one 2n bit output number that alternately takes bits from the two input numbers. That is, bits from one number goes into the odd indices, and bits from the other goes into the even indices.

So for your specific example:

x = 100101  =  1 0 0 1 0 1
y = 010101  = 0 1 0 1 0 1

interleaved = 011000110011

Here we use the convention that bits from x goes into the even indices (0, 2, 4...) and bits from y goes into the odd indices (1, 3, 5...). That is, bit interleaving is not a commutative operation; interleave(x, y) is generally not equal to interleave(y, x).

You can also generalize the bit interleaving operation to involve more than just 2 numbers.

Bit-interleaved numbers exhibit structural properties that can be taken advantage of in many important spatial algorithms/data structures.

See also

  • Wikipedia/Z-order (curve)
    • aka Morton-Order/Morton code

Related questions

  • How to compute a 3D Morton number (interleave the bits of 3 ints)
  • How to de-interleave bits (UnMortonizing?)

"Obvious" algorithm

The algorithm essentially goes through every bits of the input numbers, checking if it's 1 or 0 with bitwise-and, combining the two bits with bitwise-or, and concatenating them together with proper shifts.

To understand how the bits are rearranged, just work on a simple 4-bit example. Here xi denotes the i-th (0-based) bit of x.

x =    x3    x2    x1    x0
y = y3    y2    y1    y0
                                         Mapping:
z = y3 x3 y2 x2 y1 x1 y0 x0                 x[i] --> z[i+i]
    z7 z6 z5 z4 z3 z2 z1 z0                 y[i] --> y[i+i+1]

Once you convinced yourself that the mapping pattern is correct, implementing it is simply a matter of understanding how bitwise operations are performed.

Here's the algorithm rewritten in Java for clarity (see also on ideone.com):

    int x = Integer.parseInt("100101", 2);
    int y = Integer.parseInt("010101", 2);
    int z = 0;

    for (int i = 0; i < Integer.SIZE; i++) {
       int x_masked_i = (x & (1 << i));
       int y_masked_i = (y & (1 << i));

       z |= (x_masked_i << i);
       z |= (y_masked_i << (i + 1));
    }
    System.out.println(Integer.toBinaryString(z));
    // prints "11000110011"

See also

  • Wikipedia/Bitwise operations
Monday, August 9, 2021
 
The Coding Wombat
answered 4 Months ago
64

I'm wondering what is the optimal number of bits to examine each time

The only way to find out is to test. See this question for a discussion of the fastest way to count 32 bits at a time.

Also, if that number is not the size of some preset type, how can I walk down my bit-vector and set a pointer to be ANY arbitrary number of bits past the starting location of the bit array.

You can't set a pointer to an arbitrary bit. Most machines have byte-addressing, some can only address words.

You can construct a word starting with an arbitrary bit like so:

long wordAtBit(int32_t* array, size_t bit)
{
    size_t idx = bit>>5;
    long word = array[idx] >> (bit&31);
    return word | (array[idx+1] << (32 - (bit&31));
}
Saturday, August 21, 2021
 
Tucker
answered 4 Months ago
67

With the & operator

Thursday, October 28, 2021
 
Lightness Races in Orbit
answered 1 Month ago
48

A lot. For example when you only need to do bitwise operations on a floating-point only instruction set like AVX, then those become very handy.

Another application: making constants. You can see a lot of examples in table 13.10 and 13.11 in Agner Fog's optimization guide for x86 platforms. Some examples:

pcmpeqd xmm0, xmm0
psrld   xmm0, 30   ; 3 (32-bit)

pcmpeqd xmm0, xmm0 ; -1

pcmpeqw xmm0, xmm0 ; 1.5f
pslld   xmm0, 24
psrld   xmm0, 2

pcmpeqw xmm0, xmm0 ; -2.0f
pslld   xmm0, 30

You can also use that for checking if the floating-point value is a power of 2 or not.

Some other applications like Harold said: Taking absolute value and minus absolute value, copy sign, muxing... I'll demonstrate in a single data for easier understanding

// Absolute:
abs = x & ~(1U << 31);
// Muxing
v = (x & mask) | (y & ~mask); // v = mask ? x : y; with mask = 0 or -1
// Copy sign
y = (y & ~(1U << 31)) | (x & (1U << 31));
Thursday, November 11, 2021
 
jenny
answered 3 Weeks ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share