CODEWITHSUNDEEP
ccomparisonbit-manipulationbitwise-operators
John Riselvato
John Riselvato

Reputation: 12924

Explain this Function

Can someone explain to me the reason why someone would want use bitwise comparison? example:

int f(int x) {
return x & (x-1); 
}
int main(){
  printf("F(10) = %d", f(10));
}

This is what I really want to know: "Why check for common set bits"

x is any positive number.

Upvotes: -1

Views: 949

Answers (8)

Jim Balter
Jim Balter

Reputation: 16406

Your example tests whether x has at most 1 bit set. f returns 0 if x is a power of 2 and non-zero if it is not.

Upvotes: 0

Jason Williams
Jason Williams

Reputation: 57922

Bitwise operations are used for three reasons:

  • You can use the least possible space to store information
  • You can compare/modify an entire register (e.g. 32, 64, or 128 bits depending on your processor) in a single CPU instruction, usually taking a single clock cycle. That means you can do a lot of work (of certain types) blindingly fast compared to regular arithmetic.
  • It's cool, fun and interesting. Programmers like these things, and they can often be the differentiator when there is no difference between techniques in terms of efficiency/performance.

You can use this for all kinds of very handy things. For example, in my database I can store a lot of true/false information about my customers in a tiny space (a single byte can store 8 different true/false facts) and then use '&' operations to query their status:

  • Is my customer Male and Single and a Smoker?

    if (customerFlags & (maleFlag | singleFlag | smokerFlag) ==
    (maleFlag | singleFlag | smokerFlag))

  • Is my customer (any combination of) Male Or Single Or a Smoker?

    if (customerFlags & (maleFlag | singleFlag | smokerFlag) != 0)

  • Is my customer not Male and not Single and not a Smoker)?

    if (customerFlags & (maleFlag | singleFlag | smokerFlag) == 0)

Aside from just "checking for common bits", you can also do:

  • Certain arithmetic, e.g. value & 15 is a much faster equivalent of value % 16. This only works for certain numbers, but if you can use it, it can be a great optimisation.

  • Data packing/unpacking. e.g. a colour is often expressed as a 32-bit integer that contains Alpha, Red, Green and Blue byte values. The Red value might be extracted with an expression like red = (value >> 16) & 255; (shift the value down 16 bit positions and then carve off the bottom byte)

    • Data manipulation and swizzling. Some clever tricks can be achieved with bitwise operations. For example, swapping two integer values without needing to use a third temporary variable, or converting ARGB colour values into another format (e.g RGBA or BGRA)

Upvotes: 4

Jonathan Grynspan
Jonathan Grynspan

Reputation: 43472

The Ur-example is "testing if a number is even or odd":

unsigned int number = ...;
bool isOdd = (0 != (number & 1));

More complex uses include bitmasks (multiple boolean values in a single integer, each one taking up one bit of space) and encryption/hashing (which frequently involve bit shifting, XOR, etc.)

Upvotes: 1

ikegami
ikegami

Reputation: 386416

It's not a bitwise comparison. It doesn't return a boolean.

Bitwise operators are used to read and modify individual bits of a number.

n &   0x8   // Peek at bit3
n |=  0x8   // Set bit3
n &= ~0x8   // Clear bit3
n ^=  0x8   // Toggle bit3

Bits are used in order to save space. 8 chars takes a lot more memory than 8 bits in a char.

The following example gets the range of an IP subnet using given an IP address of the subnet and the subnet mask of the subnet.

uint32_t mask = (((255 << 8) | 255) << 8) | 255) << 8) | 255;
uint32_t ip   = (((192 << 8) | 168) << 8) |   3) << 8) |   4;

uint32_t first = ip & mask;
uint32_t last  = ip | ~mask;

Upvotes: 1

fvu
fvu

Reputation: 32973

I think you mean bitwise combination (in your case a bitwise AND operation). This is a very common operation in those cases where the byte, word or dword value is handled as a collection of bits, eg status information, eg in SCADA or control programs.

Upvotes: 0

Foo Bah
Foo Bah

Reputation: 26271

Your particular example tests if two consecutive bits in the binary representation are 1.

Upvotes: -1

Bill Lynch
Bill Lynch

Reputation: 81986

The example you've given is kinda odd, but I'll use bitwise comparisons all the time in embedded code.

I'll often have code that looks like the following:

volatile uint32_t *flags = 0x000A000;
bool flagA = *flags & 0x1;
bool flagB = *flags & 0x2;
bool flagC = *flags & 0x4;

Upvotes: 1

AndersK
AndersK

Reputation: 36102

e.g. if you have a number of status flags in order to save space you may want to put each flag as a bit.

so x, if declared as a byte, would have 8 flags.

Upvotes: 0

Related Questions