Multiplication in binary is similar to multiplication in decimal, however you're only multiplying with 0 or 1, which simplifies the math considerably.
* 0 1 0 0 0 1 0 1
Given A (some value), times 0b1010:
A
0b1010
A x 1010 ------ 0 (0 * A == 0) A0 (1 * A == A (left shifted by 1)) 000 (0 * A == 0 (left-shifted by 2, but still just 0)) + A000 (1 * A == A (left-shifted by 3)) ------ A0+A000
result ⟵ 0 while (N ≠ 0): if (N & 1): result ⟵ result + A A ⟵ A << 1 N ⟵ N >> 1
From the algorithm it should be clear that the result should have at least as many bits as A and N combined to prevent a multiplication overflow. It should also be obvious that N should be unsigned to prevent the loop from running forever (assuming that it is right shifted by the implementation.)
A sequence of characters representing an integer can be converted to an actual value by computing the numeric value for each digit and then adding/shifting the digit into its position within the integer value.
digits ⟵ "0123456789ABCDEF" base ⟵ The base of the number system (i.e. 10, 2, 16, etc) str ⟵ some string of characters representing a integer value value ⟵ 0 i ⟵ 0 while ( str[i] ≠ end of string ): value ⟵ value ∙ base str[ i ] ⟵ uppercase version of str[i] // (optional) value ⟵ value + (index of str[i] in digits) i ⟵ i + 1
value = 0 ┌─────┬─────┬─────┬──────┐ str = │ '3' │ '2' │ '6' │ '\0' │ └─────┴─────┴─────┴──────┘ ^ value = 0 * 10 == 0 value = 0 + 3 == 3 ┌─────┬─────┬─────┬──────┐ str = │ '3' │ '2' │ '6' │ '\0' │ └─────┴─────┴─────┴──────┘ ^ value = 3 * 10 == 30 value = 30 + 2 == 32 ┌─────┬─────┬─────┬──────┐ str = │ '3' │ '2' │ '6' │ '\0' │ └─────┴─────┴─────┴──────┘ ^ value = 32 * 10 == 320 value = 320 + 6 == 326
digits ⟵ "0123456789ABCDEF" str ⟵ array of characters large enough to store the number after conversion i ⟵ index at end of str str[i] ⟵ '\0' repeat: d ⟵ value % base i ⟵ i - 1 str[ i ] ⟵ digits[ d ] value ⟵ value / base until ( value = 0 )
value = 326 ┌─────┬─────┬─────┬──────┐ str = │ ' ' │ ' ' │ ' ' │ '\0' │ └─────┴─────┴─────┴──────┘ ^ d = 326 % 10 == 6 ┌─────┬─────┬─────┬──────┐ str = │ ' ' │ ' ' │ '6' │ '\0' │ └─────┴─────┴─────┴──────┘ ^ value = 326 / 10 == 32 d = 32 % 10 == 2 ┌─────┬─────┬─────┬──────┐ str = │ ' ' │ '2' │ '6' │ '\0' │ └─────┴─────┴─────┴──────┘ ^ value = 32 / 10 == 3 d = 3 % 10 == 3 ┌─────┬─────┬─────┬──────┐ str = │ '3' │ '2' │ '6' │ '\0' │ └─────┴─────┴─────┴──────┘ ^ value = 3 / 10 == 0 stop
ROM - Read Only Memory
RAM - Random Access Memory
Can be both read from and written to (i.e. read/write.)
Usually "volatile" in nature, i.e. loses its state when the power is removed.
Types:
Static RAM (SRAM) - memory built from latching "flip-flop" circuitry. Does not require being periodically "refreshed" to maintain its state. Typically the fastest type of memory, it often is used for CPU cache memory.
Dynamic RAM (DRAM) - memory that uses a capacitor alongside each bit to store a charge to maintain the state of the the bit. The capacitor must be periodically "refreshed" by either reading or writing the memory. To insure that all memory gets refreshed some of the time that the memory is available is reserved to perform these refresh operations, causing the memory to be slower overall to SRAM.
Non-Volatile RAM (NVRAM) - Currently typically used as storage, since it is over-all slower than RAM and has large write sizes (a block of data must be re-written to change a single byte,) however as the technology improves it may more usable as a primary or secondary memory.
Synchronous Dynamic RAM (SDRAM) - DRAM that uses an external timing signal to coordinate memory transactions.
Double Data Rate SDRAM (DDR SDRAM) - Doubles the effective bandwidth by allowing two reads/writes per clock cycle (uses both the rising and falling edge of the clock to synchronize transfers.)
DDR2,3,4,5 - Doubles the data rate again
GDDR - GDDR6 - Graphics DDR - Memory designed for high-bandwidth graphics processing units (GPUs).
High Bandwidth Memory (HBM) - 3D memory (stacked layers of SDRAM) that can be placed much closer to the processing unit (usually GPU) to increase bandwidth considerably.
bit - The smallest unit of memory, which is in one of two states, either electrically low or high which is usually assigned values 0 or 1.
nibble - A sub-division of 2-7 bits within a byte. 2 bits is typically called a bit-pair however.
byte - The smallest unit of addressable memory which is typically composed of a group of 8 bits.
word - Two contiguous bytes (16 bits)
double word - 4 contiguous bytes (32 bits)
quad word - 8 contiguous bytes (64 bits)
Every byte in memory has a numeric address. The amount of addressable memory depends on the size of the CPU's address bus (measured in bits) which represents the one half of the CPUs connection to memory and/or devices.
When the CPU requires more than one byte of memory, such as for an integer, which is composed of 4 consecutive bytes, then the address of the integer is the address of the first byte of that integer (i.e. the byte with the lowest address.)
In Big-endian systems the first byte is the most significant, followed by the next most significant, and so on until the last byte which is the least significant byte. Network byte order is also big-endian.
a a+1 a+2 a+3 ┌────┬────┬────┬────┐ │ 1F │ 2C │ 50 │ 23 │ └────┴────┴────┴────┘
a represents the starting address of the integer. In both above and below the number being represented is 0x1F2C5023
a
0x1F2C5023
In Little-endian systems (such as x86) the least significant byte is first, increasing in significance until the last byte which is the most significant.
a a+1 a+2 a+3 ┌────┬────┬────┬────┐ │ 23 │ 50 │ 2C │ 1F │ └────┴────┴────┴────┘
Some systems (some ARM, RISC-V, PowerPC) are Bi-endian, and can interpret numbers both ways, although the direction is often decided at boot time or via hardware and cannot be changed while running.
