Scribd
Upload
18 views8 pages

Array Problems

The document outlines a C programming task to count the number of bits set (1 bits) in a 32-bit integer, providing multiple methods for implementation. It includes examples of integers and their binary representations, as well as a separate problem related to matching nuts and bolts. Additionally, references for further reading on data structures are provided.

Uploaded by

manavasharma5465
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views8 pages

Array Problems

The document outlines a C programming task to count the number of bits set (1 bits) in a 32-bit integer, providing multiple methods for implementation. It includes examples of integers and their binary representations, as well as a separate problem related to matching nuts and bolts. Additionally, references for further reading on data structures are provided.

Uploaded by

manavasharma5465
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Problem 1 based on Arrays

❖Write a C program to count bits set in an integer?


[2]
❖ What is count bits set (number of 1 bits in binary representation of a 32 bit
number) :
Suppose integer is 5,
Binary representation is 00000000000000000000000000000101.
Count bits set =2.

Suppose integer is 10,


Binary representation is 00000000000000000000000000001010.
Count bits set =2.
16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 1
Problem 1 based on Arrays
❖ Write a C program to count bits set in an integer [2]?
❖ There are a number of ways to count the number of bits set in an
integer. Here are some C programs to do the same.
❖ Method1:

16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 2


Problems Based on Arrays
❖ Write a C program to count bits set in an integer [2]?
❖ Method 2: This is a faster way of doing the same thing. Here the control goes into the
while loop only as many times as the number of bits set to 1 in the integer!.

16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 3


Problems Based on Arrays
❖ Write a C program to count bits set in an integer [2]?
❖ Method 3:
❖ This method is very popular because it uses a lookup table.

❖ This speeds up the computation. What it does is it keeps a table which


hardcodes the number of bits set in each integer from 0 to 255.

Example: Integer Number: 250


• Binary Representation of 32 bit number 250:
00000000 00000000 00000000 11111010

16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 4


Problems Based on Arrays
❖ Write a C program to count bits set in an integer [2]?

16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 5


Problems Based on Arrays
❖ Write a C program to count bits set in an integer [2]?

Example:
Integer Number: 2511
Binary Representation in
32 bit number.

00000000 00000000
00001001 11001111
As per this solution
6+2+0+0= 08

16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 6


Problems Based on Arrays
❖ Problem: Matching Nuts & Bolts Problem (Lock & Key problem) [3]-

• Nuts represented as array of character


char nuts[] = {‘@’, ‘#’, ‘$’, ‘%’, ‘^’, ‘&’, ‘*’, ‘+’}
• Bolts represented as array of character
char bolts[] = {‘$’, ‘%’,, ‘+’ ‘&’,, ‘*’, ‘^’, ‘@’, ‘#’}

16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 7


References
1. Seymour Lipschutz, “Data Structures”, Schaum’s Series McGraw
Hill edition 2013.
2. [Link]
3. [Link]
ey-problem/

16-09-2020 Data Structure, Jasraj Meena, Dept. of IT, DTU 8

You might also like