Difference between revisions of "Intermediate C++ Game Programming Tutorial 23"

From Chilipedia
Jump to: navigation, search
(Video Timestamp Index)
(Video Timestamp Index)
 
(7 intermediate revisions by the same user not shown)
Line 12: Line 12:
 
[https://youtu.be/WPMwq0qM8Kk Tutorial 23]
 
[https://youtu.be/WPMwq0qM8Kk Tutorial 23]
 
<div class="mw-collapsible mw-collapsed"><br />
 
<div class="mw-collapsible mw-collapsed"><br />
* Converting integers to their binary representation [https://youtu.be/WPMwq0qM8Kk?t=0m15s 0:15]
+
* Converting integers to their binary representations [https://youtu.be/WPMwq0qM8Kk?t=0m25s 0:25]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** Introducing <code>std::string ToBin(unsigned int n, int min_digits=0);</code>  
+
:* Introducing <code>std::string ToBin(unsigned int n, int min_digits=0);</code>
 +
::<syntaxhighlight lang="cpp" line>
 +
std::string ToBin( unsigned int n, int min_digits = 0)
 +
{
 +
std::string bin_str;
 +
for ( int count = 0; n!=0 || count < min_digits; n>>=1,count++ )
 +
{
 +
bin_str.push_back( bool( n & 0b1 ) ? '1' : '0' );
 +
}
 +
std::reverse( bin_str.begin(),bin_str.end() );
 +
return bin_str;
 +
}
 +
</syntaxhighlight>
 
</div>
 
</div>
 
* Bitwise operators AND (<code>&</code>), OR (<code>|</code>) [https://youtu.be/WPMwq0qM8Kk?t=1m50s 1:50]
 
* Bitwise operators AND (<code>&</code>), OR (<code>|</code>) [https://youtu.be/WPMwq0qM8Kk?t=1m50s 1:50]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** Biswise AND (<code>&</code>): 1010 & 1100 = 1000, also called a mask
+
:* Biswise AND (<code>&</code>): 1010 & 1100 = 1000, also called a mask
** Biswise OR (<code>|</code>): 1010 | 1100 = 1110, also called a mash
+
:* Biswise OR (<code>|</code>): 1010 | 1100 = 1110, also called a mash
 
</div>
 
</div>
 
* Shifting operations left (<code><<</code>), right (<code>>></code>) [https://youtu.be/WPMwq0qM8Kk?t=5m10s 5:10]
 
* Shifting operations left (<code><<</code>), right (<code>>></code>) [https://youtu.be/WPMwq0qM8Kk?t=5m10s 5:10]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** Shift left (<code><<</code>): 0011 << 1 = 0110, shifts binary zeros in from the right side into the lower order bit position
+
:* Shift left (<code><<</code>): 0011 << 1 = 0110, shifts binary zeros in from the right side into the lower order bit position
** Shift right (<code>>></code>): 0110 >> 2 = 0001, shifts binary zeros in from the left side into the highter order bit position
+
:* Shift right (<code>>></code>): 0110 >> 2 = 0001, shifts binary zeros in from the left side into the highter order bit position
** Except for negative integers: <code>(-1)>>n</code>: ...1111>>2 = ...1111, shifts binary ones in from the left
+
:* Except for negative integers: <code>(-1)>>n</code>: ...1111>>2 = ...1111, shifts binary ones in from the left
 
</div>
 
</div>
* Packing and unpacking data, masking with <code>&</code> and mashing with <code>|</code> [https://youtu.be/WPMwq0qM8Kk?t=7m07s 7:07]
+
* Packing and unpacking data, masking with <code>&</code> and mashing/combining with <code>|</code> [https://youtu.be/WPMwq0qM8Kk?t=7m07s 7:07]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** Example: combining four 8-bit numbers into one 32-bit number by using <code><<</code> and <code>|</code>
+
:* Example: combining four 8-bit numbers into one 32-bit number by using <code><<</code> and <code>|</code>
** Example: unpacking a 32-bit number to an 8 bit sequence by using <code>&</code> and <code>>></code>
+
:* Example: unpacking a 32-bit number to an 8 bit sequence by using <code>&</code> and <code>>></code>
 
</div>
 
</div>
 
* Example use case: The <code>Color</code> class in the Framework [https://youtu.be/WPMwq0qM8Kk?t=12m20s 12:20]
 
* Example use case: The <code>Color</code> class in the Framework [https://youtu.be/WPMwq0qM8Kk?t=12m20s 12:20]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** XRGB 8-bit values are packed into a 32-bit word using <code>(x<<24u) | (r<<16u) | (g<<8u) | b)</code>
+
:* XRGB 8-bit values are packed into a 32-bit word using <code>(x<<24u) | (r<<16u) | (g<<8u) | b)</code>
 
</div>
 
</div>
 
* Packing flag values into a single integer parameter [https://youtu.be/WPMwq0qM8Kk?t=14m29s 14:29]
 
* Packing flag values into a single integer parameter [https://youtu.be/WPMwq0qM8Kk?t=14m29s 14:29]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** Used in libraries such as the Windows API, DirectX, in STL
+
:* Used in libraries such as the Windows API, DirectX, in STL
** Each value is represented by a single bit set in their binary representation, e.g. <code>enum Options { option1 = 0b01, option2 = 0b10 };</code>
+
:* Each value is represented by a single bit set in their binary representation
** Check for options with Bitwise AND: if you have an <code>int options</code>, check the option flag using <code>if( options & option1 )</code>
+
:* For example: <code>enum Options { option1 = 0b01, option2 = 0b10 };</code>
** Combine options with Bitwise OR: make an <code>int options = option1 | option3;</code>
+
:* Check for options with Bitwise AND: if you have an <code>int options</code>, check the option flag using <code>if( options & option1 )</code>
 +
:* Combine options with Bitwise OR: make an <code>int options = option1 | option3;</code>
 
</div>
 
</div>
 
* Advanced Bitwise operators NOT (<code>~</code>), XOR (<code>^</code>) [https://youtu.be/WPMwq0qM8Kk?t=16m48s 16:48]
 
* Advanced Bitwise operators NOT (<code>~</code>), XOR (<code>^</code>) [https://youtu.be/WPMwq0qM8Kk?t=16m48s 16:48]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** Bitwise NOT (<code>~a</code>): unary operation that flips all the bits of <code>a</code>
+
:* Bitwise NOT (<code>~a</code>): unary operation that flips all the bits of <code>a</code>
*:- Use case: switch off an option: <code>options &= ~option1;</code>
+
::- Use case: switch off an option: <code>options &= ~option1;</code>
** Bitwise XOR (<code>^</code>): binary operation sets each bit position to 1 only if the bits at that position of the two operands are different  
+
:* Bitwise XOR (<code>^</code>): binary operation sets each bit position to 1 only if the bits at that position of the two operands are different  
*:- Use case: a "configurable flipper". <code>a^0b11110000</code> will flip the 4 left bits of <code>a</code> and leave the 4 right bits the same
+
::- Use case: a "configurable flipper". <code>a^0b11110000</code> will flip the 4 left bits of <code>a</code> and leave the 4 right bits the same
*:- Toggle an option: <code>options ^= option1;</code>
+
::- Toggle an option: <code>options ^= option1;</code>
 
</div>
 
</div>
 
* Don't use Bitwise AND in logical operations like <code>if ( a & b )</code> [https://youtu.be/WPMwq0qM8Kk?t=19m49s 19:49]
 
* Don't use Bitwise AND in logical operations like <code>if ( a & b )</code> [https://youtu.be/WPMwq0qM8Kk?t=19m49s 19:49]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** <code>bool(x)</code> evaluates to false if x==0, otherwise to true
+
:* <code>bool(x)</code> evaluates to false if x==0, otherwise to true
** <code>bool( 0b01 && 0b10 )</code> is true, whereas <code>bool( 0b01 & 0b10 )</code> is false
+
:* <code>bool( 0b01 && 0b10 )</code> is true, whereas <code>bool( 0b01 & 0b10 )</code> is false
** Only reason why you would want to use <code>&</code> in logical operations is to avoid short circuiting evaluations with <code>&&</code> or <code>||</code>
+
:* Only reason why you would want to use <code>&</code> in logical operations is to avoid short circuiting evaluations with <code>&&</code> or <code>||</code>
*:- Short circuiting stops evaluating a comparison when the first argument is evaluated
+
::- Short circuiting stops evaluating a comparison when the first argument is evaluated
*:- For instance: <code>if ( false && ... )</code> will not evaluate anything after <code>&&</code> because it is irrelevant
+
::- For instance: <code>if ( false && ... )</code> will not evaluate anything after <code>&&</code> because it is irrelevant
*:- To be safe when you do this, use <code>if ( bool(a) & bool(b) )</code>
+
::- To be safe when you do this, use <code>if ( bool(a) & bool(b) )</code>
 
</div>
 
</div>
 
* Bitwise arithmetic optimizations [https://youtu.be/WPMwq0qM8Kk?t=22m30s 22:30]
 
* Bitwise arithmetic optimizations [https://youtu.be/WPMwq0qM8Kk?t=22m30s 22:30]
 
<div class="mw-collapsible-content">
 
<div class="mw-collapsible-content">
** <code>x >> n</code> divides x by 2^n (as in: 2 to the power of n)
+
:* <code>x >> n</code> divides x by 2^n (as in: 2 to the power of n)
** <code>x << n</code> multiplies x by 2^n (as in: 2 to the power of n)
+
:* <code>x << n</code> multiplies x by 2^n (as in: 2 to the power of n)
** <code>x % 16</code> is equal to <code>x & 15</code> or <code>x & 0xF</code>
+
:* <code>x % 16</code> is equal to <code>x & 15</code> or <code>x & 0xF</code>
** Note: no need to apply this in your code, the compiler will do this anyway when it optimizes
+
:* Note: no need to apply this in your code, the compiler will do this anyway when it optimizes
 
</div>
 
</div>
 
</div>
 
</div>

Latest revision as of 06:19, 5 May 2020

Bit twiddling is a lot of bullshit that is usually avoided when possible because it leads to ass code. Still, it is necessary in various situations, so you gotta learn this shit, and now is as good a time as any I guess.

Topics Covered

  • Bitwise AND (&), OR (|), and shift left/right (>> and <<)
  • Unary bitwise NOT/complement (~) and bitwise XOR (^)
  • Masking with & and combining with |
  • Packing and unpacking smaller data in larger types
  • Bit flags
  • Bitwise arithmetic optimizations

Video Timestamp Index

Tutorial 23


  • Converting integers to their binary representations 0:25
  • Introducing std::string ToBin(unsigned int n, int min_digits=0);
std::string ToBin( unsigned int n, int min_digits = 0)
{
	std::string bin_str;
	for ( int count = 0; n!=0 || count < min_digits; n>>=1,count++ )
	{
		bin_str.push_back( bool( n & 0b1 ) ? '1' : '0' );
	}
	std::reverse( bin_str.begin(),bin_str.end() );
	return bin_str;
}
  • Bitwise operators AND (&), OR (|) 1:50
  • Biswise AND (&): 1010 & 1100 = 1000, also called a mask
  • Biswise OR (|): 1010 | 1100 = 1110, also called a mash
  • Shifting operations left (<<), right (>>) 5:10
  • Shift left (<<): 0011 << 1 = 0110, shifts binary zeros in from the right side into the lower order bit position
  • Shift right (>>): 0110 >> 2 = 0001, shifts binary zeros in from the left side into the highter order bit position
  • Except for negative integers: (-1)>>n: ...1111>>2 = ...1111, shifts binary ones in from the left
  • Packing and unpacking data, masking with & and mashing/combining with | 7:07
  • Example: combining four 8-bit numbers into one 32-bit number by using << and |
  • Example: unpacking a 32-bit number to an 8 bit sequence by using & and >>
  • Example use case: The Color class in the Framework 12:20
  • XRGB 8-bit values are packed into a 32-bit word using (x<<24u) | (r<<16u) | (g<<8u) | b)
  • Packing flag values into a single integer parameter 14:29
  • Used in libraries such as the Windows API, DirectX, in STL
  • Each value is represented by a single bit set in their binary representation
  • For example: enum Options { option1 = 0b01, option2 = 0b10 };
  • Check for options with Bitwise AND: if you have an int options, check the option flag using if( options & option1 )
  • Combine options with Bitwise OR: make an int options = option1 | option3;
  • Advanced Bitwise operators NOT (~), XOR (^) 16:48
  • Bitwise NOT (~a): unary operation that flips all the bits of a
- Use case: switch off an option: options &= ~option1;
  • Bitwise XOR (^): binary operation sets each bit position to 1 only if the bits at that position of the two operands are different
- Use case: a "configurable flipper". a^0b11110000 will flip the 4 left bits of a and leave the 4 right bits the same
- Toggle an option: options ^= option1;
  • Don't use Bitwise AND in logical operations like if ( a & b ) 19:49
  • bool(x) evaluates to false if x==0, otherwise to true
  • bool( 0b01 && 0b10 ) is true, whereas bool( 0b01 & 0b10 ) is false
  • Only reason why you would want to use & in logical operations is to avoid short circuiting evaluations with && or ||
- Short circuiting stops evaluating a comparison when the first argument is evaluated
- For instance: if ( false && ... ) will not evaluate anything after && because it is irrelevant
- To be safe when you do this, use if ( bool(a) & bool(b) )
  • Bitwise arithmetic optimizations 22:30
  • x >> n divides x by 2^n (as in: 2 to the power of n)
  • x << n multiplies x by 2^n (as in: 2 to the power of n)
  • x % 16 is equal to x & 15 or x & 0xF
  • Note: no need to apply this in your code, the compiler will do this anyway when it optimizes

Homework

  • Figure out how the binary string formatter routine works
  • Figure out why x % 16 compiles to x & 0xF

The solution for the problems will not have its own video. Feel free to come on the discord and compare your answers with others, or to ask specific questions if you are having trouble understanding.

See also