{"id":19902,"date":"2023-01-19T06:17:45","date_gmt":"2023-01-19T06:17:45","guid":{"rendered":"https:\/\/www.booksofall.com\/tw\/?post_type=product&p=19902"},"modified":"2023-01-19T06:19:28","modified_gmt":"2023-01-19T06:19:28","slug":"matters-computational-ideas-algorithms-source-code","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/tw\/matters-computational-ideas-algorithms-source-code\/","title":{"rendered":"Matters Computational – Ideas, Algorithms, Source Code"},"content":{"rendered":"

Bit wizardry<\/h2>\n

We give low-level functions for binary words<\/a>, such as isolation of the lowest set bit or counting all set bits. Sometimes the term \u2018one\u2019 is used for a set bit and \u2018zero\u2019 for an unset bit. Where it cannot cause confusion, the term \u2018bit\u2019 is used for a set bit (as in \u201ccounting the bits of a word\u201d).<\/p>\n

The C-type<\/a> unsigned long is abbreviated as ulong as defined in [FXT: fxttypes.h]. It is assumed that BITS_PER_LONG reflects the size of an unsigned long. It is defined in [FXT: bits\/bitsperlong.h] and usually equals the machine word size: 32 on 32-bit architectures, and 64 on 64-bit machines. Further, the quantity BYTES_PER_LONG reflects the number of bytes in a machine word: it equals BITS_PER_LONG divided by eight. For some functions it is assumed that long and ulong have the same number of bits.<\/p>\n

Many functions will only work on machines that use two\u2019s complement, which is used by all of the current general purpose computers (the only machines using one\u2019s complement appear to be some successors of the UNIVAC system<\/a>, see [358, entry \u201cUNIVAC 1100\/2200 series\u201d]).<\/p>\n

The examples of assembler code are for the x86 and the AMD64 architecture. They should be simple enough to be understood by readers who know assembler for any CPU.<\/p>\n

Trivia<\/h3>\n

Little endian versus big endian<\/strong><\/a><\/p>\n

The order in which the bytes of an integer are stored in memory can start with the least significant byte (little endian machine) or with the most significant byte (big endian machine). The hexadecimal number 0x0D0C0B0A will be stored in the following manner if memory addresses grow from left to right:<\/p>\n

adr: z z+1 z+2 z+3
\nmem: 0D 0C 0B 0A \/\/ big endian
\nmem: 0A 0B 0C 0D \/\/ little endian<\/p>\n

The difference becomes visible when you cast pointers. Let V be the 32-bit integer with the value above. Then the result of char c = *(char *)(&V); will be 0x0A (value modulo 256) on a little endian machine but 0x0D (value divided by 224) on a big endian machine. Though friends of big endian sometimes refer to little endian as \u2018wrong endian\u2019, the desired result of the shown pointer cast is much more often the modulo operation.<\/p>\n

Whenever words are serialized into bytes, as with transfer over a network or to a disk, one will need two code versions, one for big endian and one for little endian machines. The C-type union (with words and bytes) may also require separate treatment for big and little endian architectures.<\/p>\n

Size of pointer is not size of int<\/strong><\/p>\n

If programming for a 32-bit<\/a> architecture (where the size of int and long coincide), casting pointers to integers (and back) will usually work. The same code will fail on 64-bit machines. If you have to cast pointers to an integer type, cast them to a sufficiently big type. For portable code it is better to avoid casting pointers to integer types.<\/p>\n","protected":false},"excerpt":{"rendered":"