How do I turn on a bit in an octab only if it's 0?
For example, I have the following number:
0x FF 00 FF
Now, I want the 00 part to be 1 only if it is 0. Do I need to check every byte or is there a bit trick that can be used here?
Example:
I have an unsigned long IP and I hash it with a string function, but the function is null terminated, so I need to set all null bytes to 1:
0x7F000001 (127.0.0.1, could be 0x0100007F, but platform dependent anyway)
now, i want to make 0 bytes into ones:
0x7F010101 (so it becomes 127.1.1.1)
This is the only way to do what I want is
char ip_sz[5];
*(unsigned long*)ip_sz = ulong_ip;
if (!ip_sz[0]) ip_sz[0] = 1;
if (!ip_sz[1]) ip_sz[1] = 1;
if (!ip_sz[2]) ip_sz[2] = 1;
if (!ip_sz[3]) ip_sz[3] = 1;
?
Indeed, curiosity. I don't care about performance because I know the compiler will optimize this anyway.
source to share
You can check that the entire byte is zero by applying a bit mask (i.e. a number containing the positions in the positions you want to check and zeros in all other positions * ).
In your case, you need a bit mask with eight consecutive zero positions from 7 to 15 inclusive, i.e. 0x00FF00
... If you apply a bitwise AND &
to the mask and the number n
, the result is zero only when all bits n
in positions 7 through 15 are zeros. Otherwise, the result will be some nonzero number.
int n = 0xFF00FF;
int mask = 0x00FF00;
if ((n & mask) == 0) {
... // Modify n as needed
}
You can create an eight-bit bit mask manually, or use the left shift operator:
(0xFF) // 0x000000FF
(0xFF << 8) // 0x0000FF00
(0xFF << 16) // 0x00FF0000
(0xFF << 24) // 0xFF000000
so i still have to do four
if
?
if
Not needed in this particular case , because of a little trick in C: you can use !
to convert zero to one and any other number to zero. I will illustrate this with one byte; you can use bit shifts to expand this to integers.
uint8_t n = ... // Some value
n = n | (!n); // Here is the trick
The last operation converts 0x00 to 0x01, while all other values (that is, from 0x01 to 0xFF inclusive) remain untouched ( demo ).
* The design of the bitmask depends on the operation you are applying to. For "AND" and "XOR" you mark the desired bits with ones, while for "OR" you mark them with zeros.
source to share
I googled "detect null byte in word". I advise you to do the same. It has no branch, uses five operations (at least in C, the number of machine code instructions depends on your compiler and platform, and what not). I guess you are not winning much with this, but for fun, here it is:
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
static void print(uint32_t x)
{
printf("0x%08" PRIX32 "\n", x);
}
int main()
{
uint32_t x;
x = 0xb300ff00; /* <- an example, should work with any 32 bit value */
print(x);
print(x - 0x01010101);
print((x - 0x01010101) & ~x);
print((x - 0x01010101) & ~x & 0x80808080);
print(((x - 0x01010101) & ~x & 0x80808080) >> 7);
print(x | ((x - 0x01010101) & ~x & 0x80808080) >> 7); /* <- the final result */
return 0;
}
EDIT:
As a side note, this is generated by the compiler:
leal -16843009(%rdi), %eax
movl %edi, %ecx
notl %ecx
andl %ecx, %eax
shrl $7, %eax
andl $16843009, %eax
orl %edi, %eax
One other note: this can of course work with 64-bit integers the same way, working eight bytes in parallel using the same instructions.
source to share