Cách đếm bit 1 trong số nguyên 32 bit

[Thanh_Hoang1 (Thành Hoàng)]

Em mới học thử lập trình đc mấy buổi. Cx tập code. E có thắc mắc một chỗ là làm sao để đến số các bit 1 trong 1 số nguyên 32bit và cách để code nhảy từng dòng( tức là hiện lên một dòng, ng dùng đọc xong r enter để hiện tiếp dòng sau ). Mong mn giúp đỡ ý tưởng ạ. Em cảm ơn.
P/s e ms nghĩ là dùng lặp while do. Mn giúp e vs

[toilaai4326 (Tôi Là Ai)]

This post was flagged by the community and is temporarily hidden.

[Thanh_Hoang1 (Thành Hoàng)]

À mình quên. Mình đang tập C cơ bản

[hungaya (Hung)]

unsigned int
count_ones(unsigned int num)
{
  unsigned int i = 0, count = 0;
  for (; i < 32; ++i) {
    if (num & 1) count++;
    num >>= 1;
  }
  return count;
}

[Thanh_Hoang1 (Thành Hoàng)]

Mình cảm ơn. Nhưng mình bắt buộc p dùng các công thức toán như or xor and kiểu đấy cơ. Ko đc dùng mã lệnh đếm có sẵn

[hungaya (Hung)]

Expression, có luôn, chơi kiểu lầy lội

n & 1 +
(n >> 1) & 1 +
(n >> 2) & 1 + 
(n >> 3) & 1 + 
(n >> 4) & 1 + 
...
(n >> 31) & 1

[Thanh_Hoang1 (Thành Hoàng)]

Cái này có nghĩa là nó dịch từng bit 1 r so sánh vs 1 ? Đúng ko nhỉ

[hungaya (Hung)]

Dịch sang phải sau đó thực hiện AND với 0x0001.
Tác dụng của 1 là chỉ giữ bit cuối cùng, các bit khác về 0 hết.
Hay num & 1 chỉ bằng 0 hoặc 1.

Ví dụ với integer là 8 bit:

0110.0111	1101.1010
0000.0001	0000.0001
=	=
0000.0001	0000.0000

[rogp10]

Có bit-trick đấy chịu khó tìm vậy.

[hungaya (Hung)]

Cách ngầu hơn:

unsigned int count_ones(unsigned int v)
{
	unsigned int c;
	v = v - ((v >> 1) & 0x55555555);
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
	c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
	return c;
}

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

[Thanh_Hoang1 (Thành Hoàng)]

Tks bạn. Mình hiểu hơn r