I was playing with bitwise operations and a question about counting true bits of any positive integer value, so I solved the problem with bit shifting, so I just thought if there would be some way to get shifted or unshifted bits from the bitwise operation, Code would be more optimized. So I checked the PHP documentation and I learnt bitwise operations directly translated to the C code. I checked C and I didn’t see any related section. So do you have any idea about that ? Is this possible to get these bits ? Or it just throwed away ?
The code that I’m trying to optimize :
function num1Bits($number)
{
if ($number <= 0) {
return 0;
}
$countOf1 = 0;
do {
if ($number & 1) {
++$countOf1;
}
} while ($number = $number >> 1);
return $countOf1;
}
echo num1Bits(11);
Any information would be appreciated.
10
If you are shifting x right by b bits (x >> b), then the least significant b bits will be lost. To catch them before they’re lost, you can use the bitwise and operation with a mask that contains the same number of 1 bits as you are shifting (i.e. 1 for 1 bit, 3 for 2 bits, 7 for 3 bits, 0xF for 4 bits, … ((1 << b) – 1) for b bits). E.g
lost = num & ((1 << b) - 1);
rest = num >> b;
Obviously if you are using a constant b, you can precalculate the mask value.
You’ve tagged the question with assembly as well as php and c. In assembly language (at least on some architectures), if you shift a value right by a single bit, that bit ends up stored in a flag that can then be used for various other purposes, including adding to a number. This gives an interesting approach to your problem:
mov eax, 0
mov ebx, [number to count bits in]
shr ebx, 1 ; shift right moves lsb into carry flag
adc al, 0 ; add with carry adds 0 + carry flag
shr ebx, 1
adc al, 0
; repeat another 30 times
ret ; result is in eax.
Note that there are no branching instructions at all. This makes the much faster than having to branch based on whether a 1 was shifted out or not, because that would really mess with a cpu’s branch prediction logic. A nice, clean, linear implementation is much more efficient.
The bitwise shift-left (<<) and shift-right (>>) in higher level languages such as PHP, C or C++ lose the most or least significant bit.
However, with many CPUs, the assembly instruction for shifting doesn’t really lose this bit but shift it into the carry forward flag. So you could then react on this carry flag, as explained in this SO question.
By the way in assembly, depending on your CPU, you often not only have shifting operations but also rotating instruction with or without taking into account the carry forward flag.
well certainly you just mask them off before the shift if you dont want to lose them.
Some instruction sets have a rotate which moves them around to the top, this is not reflected in high level languages (PHP, C, etc). Sometimes they rotate through the carry. Likewise as already mentioned sometimes they shift through the carry before being discarded.
If your goal is to both shift and save what is shifted off, then simply mask the bits off before shifting and save them that way, pretty much any useful programming language (has some minimal bitwise operations, and, or, not, etc) will support this.