Shift ...

[vedel]

Hello,
I know that '<<' is a SHL and '>>' is a SHR.
But I don't understand how it is used in :
'Int add = 1 << (shift-1);'
And then what is the meaning of :
'X = (Y + add)>>shift;'

Thank you in advance,

void partialButterfly4(Short *src,Short *dst,Int shift, Int line)
{
  Int j;
  Int E[2],O[2];
  Int add = 1<<(shift-1);

  for (j=0; j<line; j++)
  {    
    /* E and O */
    E[0] = src[0] + src[3];
    O[0] = src[0] - src[3];
    E[1] = src[1] + src[2];
    O[1] = src[1] - src[2];

    dst[0] = (g_aiT4[0][0]*E[0] + g_aiT4[0][1]*E[1] + add)>>shift;
    dst[2*line] = (g_aiT4[2][0]*E[0] + g_aiT4[2][1]*E[1] + add)>>shift;
    dst[line] = (g_aiT4[1][0]*O[0] + g_aiT4[1][1]*O[1] + add)>>shift;
    dst[3*line] = (g_aiT4[3][0]*O[0] + g_aiT4[3][1]*O[1] + add)>>shift;

    src += 4;
    dst ++;
  }
}  

Int add = 1<<(shift-1);
dst[0] = (g_aiT4[0][0]*E[0] + g_aiT4[0][1]*E[1] + add)>>shift;

[keskiverto]

I know that '<<' is a SHL and '>>' is a SHR.

You know that an acronym SHL exists, but you don't know what it means?

bitshift

We have a 8-bit number: 00001011 (dec 11)
We shift bits 2 positions to left and get: 00101100 (dec 44)
In other words: 11<<2 == 44

When a bit shift one position to left, its value doubles. Therefore, n<<3 is same as n*2*2*2.
Shifting right halves value, so n>>2 equals n/4.

1<<(S-1) is thus same as 1*2^(S-1)

Math would say that:
(gai + add)>>S
== gai>>S + add>>S
== gai/(2^S) + add/(2^S)
== gai/(2^S) + 1*(2^(S-1))/(2^S)
== gai/(2^S) + 1/2

However, integers don't have fractions, and shifting a bit out from either side will throw it away. Integer division does discard remainder, i.e. it does round down.

It does look like these equations attempt to round more intuitively, i.e. that 1/2->1, 3/4->1, 1/4->0, etc

[vedel]

Sorry but all what you have written, I already knew it.
I don't understand this line for example :
dst[0] = (g_aiT4[0][0]*E[0] + g_aiT4[0][1]*E[1] + add)>>shift;

They declare at the beginning 'add' which depends on 'shift', and then use them in the same line.

[vedel]

And where is the point from putting that in a loop ...

[keskiverto]

Sorry but all what you have written, I already knew it.

All?

You do realize that the 'src' is different on each iteration of loop? It is a pointer and it advances on line 20.


N = 2^shift
...
X = g_aiT4[0][0]*E[0] + g_aiT4[0][1]*E[1] + add;
dst[0] = X / N;

In other words:
Y = g_aiT4[0][0]*E[0] + g_aiT4[0][1]*E[1];
dst[0] = Y / N + 0.5f; // but without the use of floats


The 'add' adjust rounding of the division.

[vedel]

Okay, thank you keskiverto ..