In the book I am reading to learn C "The C programming language" in chapter 2.

The book is explaining Bitwise operations and it has a function that shows how many bits are in an integer.

The following is the function...

```
int Bitcount(unsigned x){
int b;
for(b = 0; x != 0; x >>=1){
if(x & 01){
b++
}
}
return b;
}
```

Then an exercise is given to us stating exactly this.

"In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x; Explain why. Use this observation to write a faster version of Bitcount".

The problem is I really cannot understand how "x &= (x-1)" would work? can someone explain this to me? or send me to a resource that could better help me understand? I have been trying to figure this out but I really can't.

Thank you for any help that you may give.

also if there is anything wrong with my question this is my first post so please help me make my questions better.

It is equivalent to `x = x & (x-1)`

Here, the & is a bitwise and, not a logical and.

So here's what happens:

1) The expression on the right will be evaluated first, and that value will be stored in x.

2) Suppose `x = 01001011`

in binary (this isn't the case, since more than 8 bits will be used to represent x, but pretend it is for this example). Then `x-1 = 01001010`

.

3) compute the bitwise and:

```
01001011 &
01001010 =
01001010
```

which deleted the rightmost one bit.

now suppose number didn't end with a 1 bit:

Say: `x = 01001100`

, the `(x-1) = 01001011`

compute the bitwise and:

```
01001100 &
01001011 =
01001000
```

again removing the rightmost 1.

Good book by the way. I hope you enjoy it!

X and X-1 cannot both have their rightmost bit set to 1, because in the binary system numbers ending in 0 and 1 alternate - so X & (X-1) is guaranteed to be a number whose rightmost bit set to 0 as AND only evaluates to true if both terms are true. Maybe the confusion stems from what Andrew W said, here a bitwise AND is used (which ANDs each bit individually)?

EDIT: now, as Inspired points out, this is only part of the answer as the original problem specifies that the rightmost 1-bit will get reset. As Andrew W already answered the correct version in detail, I'm not going to repeat his explanation here but I refer to his answer.

Let's take a closer look at the rightmost 1 bit in x: suppose `x = AAAAAA10000..0`

, where AAAAAA are arbitrary bits. Then `x-1 = AAAAAA01111..1`

. Bitwise AND of these two expressions gives `AAAAAA00000..0`

. This is how it resets the rightmost non-zero bit.

The problem is I really cannot understand how "x &= (x-1)" would work?

Binary number is positional the same way as decimal number. When we increase the number we carry a bit to the left, when we decrease we borrow from the left the same way we do with decimals. So in case `x-01`

we borrow the first 1-bit from the right while others being set to 1-bit:

```
10101000
- 00000001
--------
10100111
```

which is inversion of those bits till the first 1-bit. And as stated before by others `~y & y = 0`

that is why this method can be used to count 1-bits as proposed by the book to make the method faster comparing to bits shifting.

Similar Questions

I have a list unicode strings representing binary numbers e.g. 010110. I wish to perform bitwise operations, so how do I convert that to a structure where I can perform bitwise operations on these

Good Day RegEx Gurus, I just would like to request for some help regarding REGEX. How to find the Bitwise & operator inside a C source code? Currently I already have this RegEx: [^\&=](\&)

Given a two floating point Numbers A and B, which are command line arguments, I must create methods to do bitwise operations on them. Including And, Or, Not, xOr, floating Point addition etc... How c

My question is about how to use bitwise operators on C++ std::string. Through overloading or as function does not matter. Example for an working XOR/^ function for std::string: std::string XOR(std::st

I'm trying to convert some C# code into PHP. The C# code is as follows: strRequest=\auth\\pid\3045\ch\ehCkPNGS\resp\1529559b837decb2e0ed2f576806f10aeda4d9cdf781acd3e53ad1c3b11a20684f131229\ip\1677734

The following two C functions are equivalent: unsigned f(unsigned A, unsigned B) { return (A | B) & -(A | B); } unsigned g(unsigned A, unsigned B) { unsigned C = (A - 1) & (B - 1); return (C +

Does the Objective-C message expression (message notation) operator, which uses square brackets [], have the same precedence as the C operator for array subscripting, which also uses square brackets [

Hey I have been having trouble with a C program. The program I have to write simulates the operation of a VAX computer. I have to take in 2 variables x and y to generate z. within that there are two f

Is there a simple bitwise operation (including addition, mod etc) which can produce the following output and similar for cur=6... This is for ordering the L0 reference list with field pictures in x264

I am trying to understand how to use Bitwise AND to extract the values of individual bytes. What I have is a 4-byte array and am casting the last 2 bytes into a single 2 byte value. Then I am trying t

I have an aplication which performs some basic morphological analysis, and I am looking for an efficient means to count the number of change operations needed to transform a word into another, charact

I have seen some code for working with AD in this stackoverflow question I am getting confused about the using statement. I thought that it was just used for things that you are worried could become m

From this page, I got to know that operator precedence of Bitwise AND is higher than Logical OR. However, the following program gives an unexpected output. #include<iostream> using namespace st

I have a unsigned integer N = abcd where a,b,c,d represents bits from msb to lsb. I want get following numbers x1 = ab0cd x2 = ab1cd What is the fastest way to do it using bitwise operations in C? Wh

Is there a direct way how to turn a negative number to positive using bitwise operations in Actionscript 3? I just think I've read somewhere that it is possible and faster than using Math.abs() or mul

How can I draw just a pixel in C programming? I feel if I know this, I can build a whole lot of codes for drawing many objects line, circle etc. I am using fedora 17 (linux) on intel chip. Am I bei

When I give to a variable such value: e = 17|-15; , I get -15 as an answer after compiling.I can't understand what arithmetic c++ uses. How does it perform a bit-wise OR operation on negative decimals

I've been teaching myself in C programming with the book recommended by a friend who is great in C. The book title is Programming in C by Stephen Kochan. I have a background in Java, and I feel a li

I'm re-writing some old application in VB.NET to C# and ASP.NET 3.5. Everything is going OK but I have this problem - and, as the database will not be changed, I must find a solution to it. The old ap

I want a one line code to check whether a given integer is of form 2i - 2j or NOT. (using bitwise operators) I tried to do it but I don't seem to be getting the answer. Can anyone please help me with

I am operating on individual bits of two integers, (i am using g++ for compilation on Ubuntu machine). In some intermediate step, I have the bit representations as q = 1100000000000000000000000000000

This is in relation to a homework assignment but this is not the homework assignment. I'm having difficultly understanding if there is a difference on how the bitwise not (~ in C) would affected sign

I have a DataColumn implementation to evaluate expressions at runtime. For my surprise, DataColumn operations seens not to support bitwise operators. In need to check for individual bits set or group

Possible Duplicate: How to reverse bitwise AND (&) in C? If I am using bitwise AND 7758194 & 255 = 114 how could I get back 7758194, given the result 114?

I've been looking at bitwise operations as a way of speeding things up in critical areas. But most of what I find are just low level explanations. Would anyone be so kind as to briefly explain what pr

I'm trying to write a function that will accept a bitwise combination of my enum constants. typedef enum { one = 1 << 0, two = 1 << 1, three = 1 << 2 } num; void myFunc(num nums) { p

I was reading the SO question about displaying integers as hex using C (without using %x, by using a custom function) and the first answer mentions using bitwise operators to achieve the goal. But I c

Can any one suggest me a Best IDE for C programming ( With auto completion feature)?

Can someone explain ARM bit-shifts to me like I'm five? I have a very poor understanding of anything that involves non-decimal number systems so understanding the concepts of bit shifts and bitwise op

I'm reading Programming in C by Kochan, 3rd ed. In the introduction to arrays (program 7.1) he gives an example: #include <stdio.h> int main(void) { int values[10]; int index; values[0] = 197; v

How exactly do the following lines work if pData = abc? pDes[1] = ( pData[0] & 0x1c ) >> 2; pDes[0] = ( pData[0] << 6 ) | ( pData[1] & 0x3f );

This question already has an answer here: Android AsyncTask for Long Running Operations 4 answers I'm confused by what I read about the AsyncTask. On one hand, the android document states that

I am receiving 2 bytes of binary information via Serial in C. I am receiving them in a char. So I need to join the 2 chars to make a int but Im unsure how to do that.. first of all the first byte is i

I am looking for a way that I can do bitwise operations (for crypto so mostly xor) on hex strings which could possibly be longer than I would want to fit in a Long. As an example I could have a length

Whats the easiest way to find out what programming language an application was written in? I would like to know if its vb or c++ or delphi or .net etc from the program exe file.

what's the best way to perform bitwise operations on vector<bool>? as i understand, vector<bool> is a specialisation that uses one bit per boolean. I chose vector<bool> for memory sa

Using ordinary C, I wish to compare two 8 bit bytes to determine if the second is the bitwise complement of the first. For example if Byte1 is binary 00001111 (15 in decimal) I want to test whether

I'm currently learning Obj-C for the purpose of iOS programming, but there are some concepts that I am confused about. Specifically, the getter and setter accessors. I'm reading several different thin

How can I perform the operations done by gacutil, like installing assemblies or listing the contents of the GAC, programatically in C#? Or to put it another way, is gacutil layered on top of a public

When you cast a character to an int in C, what exactly is happening? Since characters are one byte and ints are four, how are you able to get an integer value for a character? Is it the bit pattern th

I'm trying to do some bitwise operations in Javascript, 0xff000000 | 0x00aabbcc Which I expect to give me 0xffaabbcc // == 4289379276; However when running this, I get the result -5588020. I expect

I am new to bitwise operators. I understand how the logic functions work to get the final result. For example, when you bitwise AND two numbers, the final result is going to be the AND of those two nu

Somehow, JavaScript makes sense of the bitwise operations NaN ^ 1, Infinity ^ 1 and even 'a' ^ 1 (all evaluate to 1). What are the rules governing bitwise operators on non numbers? Why do all the exam

So I have an assignment that I have to code a function in c that uses only the bitwise operations of ~ , & , ^ , | , + , << , >> , and =. I have to use only 20 operations. And I am not

I need operations like: ls -r, mv, copy, delete, rm -rf to call from C program. What is the best way? To call these command by calling the system() call or by writing by myself these functionality?

Possible Duplicate: Method Syntax in Objective C I just started learning objective C and I'm a little confused about this statement. +(NSMutableArray *) array; This is what I understand: + means t

I'm trying to create a char (8 bits) with bit operations, one hex at a time. The machine I'm running on is little endian. So anyways, for example: char buff; buff = 0x54; // ('T') printf( %c \n, buf

I'm trying to optimize my chess program. I'm using ulong bitboards to generate legal moves as I thought it would be very quick. Profiler, however, suggests that much of the time is spent on bitwise AN

I am a Theoretical Physics research student, working in Cosmology. In course of my research I have use to rather huge library of Fortran codes and I used C for my programming needs. I have been able

Firstly, let me just state for the record that this is in prep for a midterm I have Wednesday. I'm taking a C Programming course and we've barely even touched Bitwise Operations, but we're being teste