bitwise and operator

The Partridge Family were neither partridges nor a family. Discuss.
User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

bitwise and operator

Post by Yumtard » January 23rd, 2018, 10:38 am

I'm a bit confused about the code below. What exactly does (i & 1) mean here?

Code: Select all

for (int i = 0; i < 8;i++) 
{ 
offset.x = ((i & 1) ? step : -step); 
offset.y = ((i & 2) ? step : -step); 
offset.z = ((i & 4) ? step : -step); 
pNode->pChild[i] = BuildOctree(center + offset, step, stopDepth - 1); 
}

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: bitwise and operator

Post by cyboryxmen » January 23rd, 2018, 3:09 pm

Looks like super fancy code used to initialise all 8 children of the node. Normally, you can just use 3 for loops for this: one going 0-1 for z, another going 0-1 for y and one more going 0-1 for x. This guy is going for something more clever(and probably slower) by using the bits of the number. Each individual bit naturally go from 0 and 1 already and you can get every combination of them from x:0y:0z:0 to x:1y:1z:1 by counting from 0 to 7. Watch:

0:000
1:001
2:010
3:011
4:100
5:101
6:110
7:111

I'm not entirely sure of the reason for this procedure. Having 3 loops won't take up that much space or at least not to the point where you use a bitmask to save space.
Zekilk

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: bitwise and operator

Post by Yumtard » January 23rd, 2018, 3:23 pm

Yeah I understand what it's doing now, thanks :)

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: bitwise and operator

Post by Yumtard » January 23rd, 2018, 4:29 pm

seems to me that i & 4 should be replaced with i & 3 tho

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: bitwise and operator

Post by cyboryxmen » January 23rd, 2018, 5:30 pm

Yumtard wrote:seems to me that i & 4 should be replaced with i & 3 tho
That's just how bitwise and works. 4 translates to 0100 in binary so it'll get the third bit. 3 translates to 0011 which will get the first and second. We only want the third bit here so 4 makes more sense
Zekilk

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: bitwise and operator

Post by albinopapa » January 23rd, 2018, 7:08 pm

That's kind of funny you posted this, I was thinking of posting something similar a couple days ago. It was about how you could use bitwise & instead of % to separate the even and odd loops.

Code: Select all

for( size_t i = 0; i < count; ++i )
{
     // using % modulo
     if( i % 2 == 0 )
     
     // using & bit and
     if( i & 2 == 0 )
}
I'm not sure how the circuitry works out, but % is a division, multiplication and subtraction in one instruction. So for this type of op, I would imagine bit & would be more efficient...not tested though.
The other thing I was thinking was, if you have a mesh and wanted to load in your vertices into triangles, you could do i&3 from 0 to vert_count

Code: Select all

for i = 0 to vert_count, i++
     j = i & 3
     triangle[j].vertex[i] = vertex[i]
end
Though, during initialization, optimization tricks like this are useless. Who cares about initialization speed right? That is, if this is even any faster than:

Code: Select all

for i = 0 to vertex_count, i++
     j = i % 3
     triangle[j].vertex[i] = vertex[i]
end

// or

for j = 0 to vertex_count / 3, j++
     i = j * 3
     triangle[j].vertex[i] = vertex[i++]     // i = j + 0
     triangle[j].vertex[i] = vertex[i++]     // i = j + 1
     triangle[j].vertex[i] = vertex[i]         // i = j + 2
end
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: bitwise and operator

Post by Yumtard » January 23rd, 2018, 9:53 pm

cyboryxmen wrote:
Yumtard wrote:seems to me that i & 4 should be replaced with i & 3 tho
That's just how bitwise and works. 4 translates to 0100 in binary so it'll get the third bit. 3 translates to 0011 which will get the first and second. We only want the third bit here so 4 makes more sense

I was a bit confused. I thought the 4 meant "bit number 4" but think I get it now

so if (i & 4) basically means if i and 4 == 4?
But then how would i & 3 work?

so it would be

0000
0100
false

0001
0100
false

0010
0100
false

0011
0100
false

0100
0100
true

0101
0100
true

0110
0100
true

0111
0100
true

and so on, a series of 4 false followed by 4 true

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: bitwise and operator

Post by albinopapa » January 23rd, 2018, 10:03 pm

sind 3 is 011, you'll always get numbers between 0 and 3 inclusive.

0000'0000 & 0011 = 0 // 0 & 3
0000'0001 & 0011 = 1 // 1 & 3
0000'0010 & 0011 = 2 // 2 & 3
0000'0011 & 0011 = 3 // 3 & 3
0000'0100 & 0011 = 0 // 4 & 3
0000'0101 & 0011 = 1 // 5 & 3
0000'0110 & 0011 = 2 // 6 & 3
0000'0111 & 0011 = 3 // 7 & 3
0000'1000 & 0011 = 0 // 8 & 3
0000'1001 & 0011 = 1 // 9 & 3
0000'1010 & 0011 = 2 // 10 & 3
0000'1011 & 0011 = 3 // 11 & 3
0000'1100 & 0011 = 0 // 12 & 3
0000'1101 & 0011 = 1 // 13 & 3
0000'1110 & 0011 = 2 // 14 & 3
0000'1111 & 0011 = 3 // 15 & 3
...
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: bitwise and operator

Post by Yumtard » January 23rd, 2018, 10:10 pm

yeah but if I were to make it a condition

if (x & 3)

am I correct in assuming this would be true whenever x & 3 == 3 and otherwise false?

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: bitwise and operator

Post by albinopapa » January 23rd, 2018, 10:17 pm

No, what about
if( 2 & 3 ) ? // expands to if( 2 ) which is not 0, so it takes the true path.

or

if( 5 & 3 )? // expands to if( 1 ) which again is not 0, so it takes the true path
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply