Find the number of bits that are different between the two integers

© Parineeth M R

Question 32. Given two integers, find the number of bits that are different between the two integers


Consider the integers 2 (0010 in binary) and 9 (1001). Three bits are different and one bit is identical. To efficiently find the number of bits that are different, we do the following

1. XOR the two integers.

2. In the result of the XOR, if the bit is 1, then the two integers are different at this bit position. So the number of 1’s present in the result gives the number of different bits between the two integers. For counting the number of 1’s in the result, we make use of the technique we described in problem 29

C/C++


/*
a, b: the two input integers
Return value: Number of bits that have different values in a and b
*/
unsigned int count_different_bits(unsigned int a, unsigned int b)
{
	unsigned int c = a ^ b; 
	unsigned int count = 0;

	/*Since c = a xor b, the positions where a and b are different will 
	be set to 1 in c. So by counting the number 1's in c, we will get the 
	number of bits that are different between a and b*/
	while (c != 0) {
		count++;
		c = c & (c - 1);
	}

	return count;
}



Java


/*
a, b: the two input integers
Return value: Number of bits that have different values in a and b
*/
public static int countDifferentBits( int a,  int b) {
	 int c = a ^ b;
	 int count = 0;

	/*Since c = a xor b, the positions where a and b are different will 
	be set to 1 in c. So by counting the number 1's in c, we will get the
	number of bits that are different between a and b*/
	while (c != 0) {
		count++;
		c = c & (c - 1);
	}

	return count;
} 



Python


#a, b: the two input integers
#Return value: Number of bits that have different values in a and b
def count_different_bits( a,  b) :
	c = a ^ b
	count = 0

	#Since c = a xor b, the positions where a and b are different will 
	#be set to 1 in c. So by counting the number of 1's in c, we will get the
	#number of bits that are different between a and b
	while (c != 0) :
		count += 1
		c = c & (c - 1)
	
	return count     



Reverse the bits in an integer

© Parineeth M R

Question 31. Reverse the bits in an integer


We can reverse the bits in an integer one bit at a time. However there is a faster technique. To reverse the bits in an integer efficiently, a lookup table is pre-computed to give the reverse values for every byte. This lookup table is then referred to for performing the reversal of the integer. The code for this is given below

C/C++


/*
input_value: the integer that has to be reversed
reverse_table: lookup table that has the reversed values for every byte.
	Example - reverse_table[0x1] = 0x80, since reverse of 00000001 is 1000000
Return value: integer that is the reverse of the input integer
*/
unsigned int reverse_integer(unsigned int input_value, 
				unsigned char reverse_table[])
{
	unsigned int result = 0;
	int i = 0;
	int num_bytes = sizeof(int);

	for (i = 0; i < num_bytes; ++i) {
		/*Get the least significant byte from the input*/
		int cur_byte_value = input_value & 0xFF;

		/*Left shift the result by 8 and append the reverse of the 
		LS byte of input*/
		result = (result << 8) | reverse_table[cur_byte_value];

		/*Right shift out the least significant byte from the input*/
		input_value = input_value >> 8;
	}
	return result;
}




Java


/*
inputValue: the integer that has to be reversed
reverseTable: lookup table that has the reversed values for every byte.
	 Example - reverseTable[0x1] = 0x80, since reverse of 00000001 is 1000000
Return value: integer that is the reverse of the input integer
*/
public static int reverseInteger( int inputValue,  char[] reverseTable) {
	int result = 0;
	int i = 0;
	int numBytes = 4;

	for (i = 0; i < numBytes; ++i) {
		/*Get the least significant byte from the input*/
		int curByteValue = inputValue & 0xFF;

		/*Left shift the result by 8 and append the reverse of the 
		LS byte of input*/
		result = (result << 8) | reverseTable[curByteValue];

		/*Right shift out the least significant byte from the input*/
		inputValue = inputValue >> 8;
	}

	return result;
}




Python


#input_value: the integer that has to be reversed
#reverse_table: lookup table that has the reversed values for every byte.
#	Example: reverse_table[0x1] = 0x80, since reverse of 00000001 is 1000000
#Return value:  integer that is the reverse of the input integer
def reverse_integer(input_value,  reverse_table) :
	result = 0
	num_bytes = 4
	for  i in range(0, num_bytes):
		#Get the least significant byte from the input
		cur_byte_value = input_value & 0xFF
		
		#Left shift the result by 8 and append the reverse of the 
		#least significant byte of input		
		result = (result << 8) | reverse_table[cur_byte_value]

		#Right shift out the least significant byte from the input
		input_value = input_value >> 8
	
	return result



Find if an integer is a power of 2

© Parineeth M R

Question 30. Find if an integer is a power of 2 using bit wise operators


The condition (x & (x-1) == 0) checks if an integer is a power of 2 or not. From the previous question, we know that x & (x-1) will reset the first bit that has a value of 1 from the right to 0. If x is a power of 2, then only one of the bits will be set to 1 and all the remaining bits will be set to 0 (for instance, 8 is a power of 2 and 8 in binary is 1000). So x & (x-1) will reset the only bit that has a value of 1 resulting in 0.

x & (x-1) == 0 however incorrectly indicates that 0 is also a power of 2, since (0 & (0 – 1) ) = (0 & 0xffffffff) = 0. Since 0 is not a power of 2, we modify the condition as shown below

C/C++


(x != 0) && (x & (x-1) == 0)


Java


(x != 0) && ((x & (x-1)) == 0)


Python


(x != 0) and ((x & (x-1)) == 0)


Efficiently count the number of bits set in an integer

© Parineeth M R

Question 29. Efficiently count the number of bits set in an integer


One way to find the number of bits set in an integer is to check each bit. However there is a faster method to count the number of bits set using the function below

C/C++


unsigned int count_num_bits_set(unsigned int n)
{
	unsigned int count = 0;
	
	while (n) {
		n &= n - 1;
		count++;
	}

	return count;
}



Java


public static int countNumBitsSet(int n) {
	int count = 0;

	while (n != 0) {
		n &= n - 1;
		count++;
	}

	return count;
}



Python


#Returns the number of bits set to 1 in n
def count_num_bits_set(n) :
	count = 0

	while (n != 0) :
		n &= n - 1
		count += 1
	
	return count



The following code works because each time we perform the operation n &= n – 1, the first bit that has a value of 1 from the right (from the least significant bit) is reset to 0.

For instance if n = 1100, then

So 1100 is converted to 1000 where in the first bit that has a value of 1 from the right in 1100 is now reset to 0.

Convert a string having Roman numerals to an integer

© Parineeth M R

Question 27. Convert a string having Roman numerals into an integer


The integer equivalent for the roman numerals is given below

To find the integer equivalent of a string containing roman numerals, we process the string from the rear. This simplifies the computation. If the current roman numeral is greater than the next numeral, we add the current numeral to the result. For instance consider XI. When processing X, since X is greater than I, we add 10 to the result. If the current roman numeral is less than the next numeral, then we subtract the current numeral from the result. For instance consider IX. When processing I, since I is less than X, we subtract 1 from the result.

C/C++


/*Helper function that returns the numeric value of a Roman alphabet*/
int get_numeric_value(char c)
{
	int result;

	switch(c) {
		case 'I': result = 1; break;
		case 'V': result = 5; break;
		case 'X': result = 10; break;
		case 'L': result = 50; break;
		case 'C': result = 100; break;
		case 'D': result = 500; break;
		case 'M': result = 1000; break;
		default: result = 0; break;
	}
	return result;
}


/* 
Main function that converts a Roman string into an integer
str1: valid input string with Roman alphabets
Return value: integer equivalent of the Roman string
*/
int roman_to_int(char *str1) 
{
	int i, result;
	
	/*Process the string from the rear*/
	i = strlen(str1) - 1;
	if (i < 0)
		return 0;
	
	result = get_numeric_value(str1[i]);
	--i;
	while (i >= 0) {
		int cur_value = get_numeric_value(str1[i]);
		int next_value = get_numeric_value(str1[i+1]);

		if (cur_value < next_value)
			result -= cur_value;
		else
			result += cur_value;		
			
		--i;
	}
	
	return result;
}



Java


/*Helper function that returns the numeric value of a Roman alphabet*/
public static int getNumericValue(char c) {
	int result;

	switch(c) {
		case 'I': result = 1; break;
		case 'V': result = 5; break;
		case 'X': result = 10; break;
		case 'L': result = 50; break;
		case 'C': result = 100; break;
		case 'D': result = 500; break;
		case 'M': result = 1000; break;
		default: result = 0; break;
	}
	return result;
}

/* 
Main function that converts a Roman string into an integer
str1: valid input string with Roman alphabets
Return value: integer equivalent of the Roman string
*/
public static int romanToInt(char[] str1) {
	/*Process the string from the rear*/		
	int i = str1.length - 1;
	if (i < 0)
		return 0;

	int result = getNumericValue(str1[i]);
	--i;
	while (i >= 0) {
		int curDigitVal = getNumericValue(str1[i]);
		int nextDigitVal = getNumericValue(str1[i+1]);

		if (curDigitVal < nextDigitVal)
			result -= curDigitVal;
		else
			result += curDigitVal;		
		
		--i;
	}

	return result;
}



Python


#str1: valid input string with Roman alphabets
#Return value: integer equivalent of the Roman string
def roman_to_int(str1) :
	table = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	
	i = len(str1) – 1 #Process the string from the rear
	if (i < 0):
		return 0

	result = table[str1[i]]
	i -= 1
	while (i >= 0) :
		cur_digit_val = table[str1[i]]
		next_digit_val = table[str1[i+1]]
		if (cur_digit_val < next_digit_val):
			result -= cur_digit_val
		else:
			result += cur_digit_val		
		i -= 1
	
	return result



Print a number in words

© Parineeth M R

Question 26. Given a number from 0 to 999,999,999, print the number in words. So 200,145,700 should be printed as two hundred million one hundred forty five thousand seven hundred


We will break the input number into millions, thousands and the remaining 3 least significant digits. So in this case 200,145,700 gets broken down to 200, 145 and 700. Then we make use of a helper function that prints 3 consecutive digits.

C/C++


/* 
Helper function to print number from 1 to 999
number: number from 1 to 999
*/
void print_3_digits(int number)
{
	int hundreds_digit, tens_digit, unit_digit, remainder;

	/*basic_lookup[0] is empty. We want basic_lookup[1] to map to "One" 
	and so on. */
	char *basic_lookup[] = {"", "One", "Two", "Three", "Four", "Five", "Six",
			"Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", 
			"Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen",
			"Eighteen", "Nineteen"};

	/*tens_lookup[0] and tens_lookup[1] are empty.
	We want tens_lookup[2] to map to "Twenty" and so on. */
	char *tens_lookup[] = {"", "","Twenty", "Thirty", "Fourty", "Fifty", 
			"Sixty", "Seventy", "Eighty", "Ninety"};

	/*Suppose number is 987, then hundreds_digit is 9*/
	hundreds_digit = number / 100;
	if (hundreds_digit > 0) {
		printf("%s Hundred ", basic_lookup[hundreds_digit]);
	}
	
	/*Suppose number is 987, then remainder will be 87*/
	remainder = number % 100;
	if (remainder > 0) {
		if (remainder <= 19) {
			printf("%s ", basic_lookup[remainder]);			
		} else {
			tens_digit = remainder / 10;
			unit_digit = remainder % 10;
			printf("%s ", tens_lookup[tens_digit]);
			printf("%s ", basic_lookup[unit_digit]);
		}
	}
	
}
 
/*
Main function to print the number in words
number: any number from 0 to 999999999
*/
void print_num_in_words(int number)
{
	int millions, thousands, remainder;

	/*If number is 0, handle it here and return*/
	if (number == 0) {
		printf("Zero \n");
		return;
	}

	/*Suppose number is 123456789, then millions = 123, remainder = 456789*/
	millions = number / 1000000;
	remainder = number - (millions * 1000000);
	
	/*Suppose remainder = 456789, then thousands = 456, remainder = 789*/
	thousands = remainder / 1000;
	remainder = remainder - (thousands * 1000);

	if (millions > 0) {
		print_3_digits(millions);
		printf("Million ");
	}

	if (thousands > 0) {
		print_3_digits(thousands);
		printf("Thousand ");
	}

	if (remainder > 0) {
		print_3_digits(remainder);
	} 
	
	printf("\n");
}



Java


/* 
Helper function to print number from 1 to 999
number: number from 1 to 999
*/
public static void print3Digits(int number) {
	/*basicLookup[0] is empty. We want basicLookup[1] to map to "One"
	and so on. */
	String[] basicLookup = {"", "One", "Two", "Three", "Four", "Five", 
			"Six", "Seven", "Eight", "Nine", "Ten", "Eleven", 
			"Twelve", "Thirteen", "Fourteen", "Fifteen", 
			"Sixteen", "Seventeen",	"Eighteen", "Nineteen"};

	/*tensLookup[0] and tensLookup[1] are empty.
	We want tensLookup[2] to map to "Twenty" and so on. */
	String[] tensLookup = {"", "","Twenty", "Thirty", "Fourty", "Fifty",
			"Sixty", "Seventy", "Eighty", "Ninety"};

	/*Suppose number is 987, then hundredsDigit is 9*/
	int hundredsDigit = number / 100;
	if (hundredsDigit > 0) {
		System.out.print(basicLookup[hundredsDigit] + " Hundred ");
	}

	/*Suppose number is 987, then remainder will be 87*/
	int remainder = number % 100;
	if (remainder > 0) {
		if (remainder <= 19) {
			System.out.print(basicLookup[remainder] + " ");			
		} else {
			int tensDigit = remainder / 10;
			int unitDigit = remainder % 10;
			System.out.print(tensLookup[tensDigit] + " ");
			System.out.print(basicLookup[unitDigit] + " ");
		}
	}
}
 
/*
Main function to print the number in words
number: any number from 0 to 999999999
*/
public static void printNumInWords(int number) {
	/*If number is 0, handle it here and return*/
	if (number == 0) {
		System.out.println("Zero ");
		return;
	}

	/*Suppose number is 123456789, then millions = 123, remainder = 456789*/
	int millions = number / 1000000;
	int remainder = number - (millions * 1000000);

	/*Suppose remainder = 456789, then thousands = 456, remainder = 789*/
	int thousands = remainder / 1000;
	remainder = remainder - (thousands * 1000);

	if (millions > 0) {
		print3Digits(millions);
		System.out.print("Million ");
	}

	if (thousands > 0) {
		print3Digits(thousands);
		System.out.print("Thousand ");
	}

	if (remainder > 0) {
		print3Digits(remainder);
	} 

	System.out.println("");
}



Python


#Helper function to print number from 1 to 999
#number: number from 1 to 999
def print_3_digits(number) :
	#basic_lookup[0] is empty. We want basic_lookup[1] to map to 'One'
	#and so on. 
	basic_lookup = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 
			'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve',
			'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 
			'Seventeen', 'Eighteen', 'Nineteen']

	#tens_lookup[0] and tens_lookup[1] are empty.
	#We want tens_lookup[2] to map to 'Twenty' and so on. 
	tens_lookup = ['', '','Twenty', 'Thirty', 'Fourty', 'Fifty', 'Sixty',
			'Seventy', 'Eighty', 'Ninety']

	#Suppose number is 987, then hundreds_digit is 9
	hundreds_digit = number // 100
	if (hundreds_digit > 0) :
		print(basic_lookup[hundreds_digit] + ' Hundred ', end='')
	

	#Suppose number is 987, then remainder will be 87
	remainder = number % 100
	if (remainder > 0) :
		if (remainder <= 19) :
			print(basic_lookup[remainder] + ' ', end='')
		else :
			tens_digit = remainder // 10
			unit_digit = remainder % 10
			print(tens_lookup[tens_digit] + ' ', end='')
			print(basic_lookup[unit_digit] + ' ', end='')
 
#Main function to print the number in words
#number: any number from 0 to 999999999
def print_num_in_words(number) :
	#If number is 0, handle it here and return
	if (number == 0) :
		print('Zero ')
		return
	
	#Suppose number is 123456789, then millions = 123, remainder = 456789
	millions = number // 1000000
	remainder = number - (millions * 1000000)

	#Suppose remainder = 456789, then thousands = 456, remainder = 789
	thousands = remainder // 1000
	remainder = remainder - (thousands * 1000)

	if (millions > 0) :
		print_3_digits(millions)
		print('Million ', end='')
	
	if (thousands > 0) :
		print_3_digits(thousands)
		print('Thousand ', end='')
	
	if (remainder > 0) :
		print_3_digits(remainder)
	 
	print('')




Convert a string to an integer

© Parineeth M R

Question 25. Convert a string to an integer without using built-in functions


The function for converting a string to an integer is given below:

C/C++


/*
str: string to be converted to an integer
Result: integer value of the string
*/
int function_atoi(const char * str)
{
	int i, length; 
	int val = 0;
	int is_negative = 0;

	if (!str)
		return 0;

	length = strlen(str);
	i = 0;
	if (str[0] == '-') {
		is_negative = 1;
		++i;
	} 

	while (i < length ) {
		if (str[i] >= '0' && str[i] <= '9') {
			val = (val * 10) + (str[i] - '0');
		}
		else {
			break;
		}
		++i;
	}
	
	if (is_negative)
		val = -1 * val;

	return val;
}



Java


/*
str1: string to be converted to integer
result: integer value of string
*/
public static int strToInt(char[] str1) {
	int result = 0;
	boolean isNegative = false;
	int count = 0;
	
	for (char c : str1) {
		if (c == '-' && count == 0)
			isNegative = true;
		
		if ('0' <= c && c <= '9') 
			result = (result * 10) + (c - '0');

		count++; 
	}

	if (isNegative)
		result = -1 * result;

	return result;
}



Python


#str1: string to be converted to integer
#result: integer value of string
def str_to_int(str1):
	result = 0
	count = 0
	is_negative = False

	for c in str1:
		if (c == '-' and count == 0):
			is_negative = True

		if ('0' <= c and c <= '9'):
			result = (result * 10) + (ord(c) - ord('0'))

		count += 1

	if (is_negative):
		result = -1 * result 
		
	return result



Count number of words in a string

© Parineeth M R

Question 24. Count the number of words in a string


We will define a word as a collection of one or more characters from a-z and A-Z. The words in a string can be separated by multiple spaces, tabs, punctuation marks etc. To count the number of words, as we traverse the string we will keep track of the previous character and the current character. If the previous character is not an alphabet from a-z and A-Z and the current character is an alphabet from a-z and A-Z, then we have encountered a new word and we increase the word count by 1.

C/C++


/*
str1: string in which the number of words have to be counted
Return value: number of words in the string
*/
int count_words(char *str1) 
{
	int num_words, pos;
	char cur_char, is_prev_char_alphabet;

	if (!str1)
		return 0;

	num_words = 0;
	pos = 0;
	cur_char = str1[pos];
	is_prev_char_alphabet = 0;
	while (cur_char != '\0') {
		int is_cur_char_alphabet = is_alphabet(cur_char);

		/*If previous character is not an alphabet and current character
		is an alphabet then we have found a new word*/
		if (!is_prev_char_alphabet && is_cur_char_alphabet) {
			++num_words;
		}

		is_prev_char_alphabet = is_cur_char_alphabet;
		
		pos++;
		cur_char = str1[pos];		
	}

	return num_words;
}

/*Helper function which checks if a character is an alphabet(a-zA-Z)*/
int is_alphabet(char c)
{
	if (c >= 'A' && c <= 'Z')
		return 1;

	if (c >= 'a' && c <= 'z')
		return 1;

	return 0;		
}



Java


/*
str1: string in which the number of words have to be counted
Return value: number of words in the string
*/
public static int countWords(char[] str1) {
	if (str1 == null)
		return 0;

	int numWords = 0;
	boolean isPrevCharAlphabet = false;
	for (char c : str1) {
		boolean isCurCharAlphabet = isAlphabet(c);

		/*If previous character is not an alphabet and current character is 
		an alphabet then we have found a new word*/
		if (!isPrevCharAlphabet && isCurCharAlphabet) 
			++numWords;

		isPrevCharAlphabet = isCurCharAlphabet;
	}

	return numWords;
}

/*Helper function which checks if a character is an alphabet(a-zA-Z)*/
public static boolean isAlphabet(char c)	{
	if (c >= 'A' && c <= 'Z')
		return true;

	if (c >= 'a' && c <= 'z')
		return true;

	return false;		
}



Python


#str1: string in which the number of words have to be counted
#Return value: number of words in the string
def count_words(str1) :
	if (str1 == None):
		return 0

	num_words = 0
	is_prev_char_alphabet = False
	for c in str1 :
		is_cur_char_alphabet = is_alphabet(c)

		#If previous character is not an alphabet and current character is 
		#an alphabet then we have found a new word
		if (not is_prev_char_alphabet and is_cur_char_alphabet) :
			num_words += 1
		
		is_prev_char_alphabet = is_cur_char_alphabet
	
	return num_words

#Helper function which checks if a character is an alphabet(a-zA-Z)
def is_alphabet(c):
	if (c >= 'A' and c <= 'Z'):
		return True

	if (c >= 'a' and c <= 'z'):
		return True

	return False



Find if two strings are anagrams

© Parineeth M R

Question 23. Find if two string words are anagrams of each other


Two strings are anagrams of each other if re-arrangement of characters in one string results in the other string. This implies that two string words are anagrams if for each character, the number of times the character occurs in the first string is equal to the number of times it occurs in the second string. The code for finding if two words are anagrams is given below

C/C++


/*str1, str2: the two non-NULL strings which we want to compare
Return value: 1 if the two strings are anagrams, 0 otherwise
*/
int are_strings_anagrams( char *str1, char *str2)
{
	int count1[NUM_CHARACTERS], count2[NUM_CHARACTERS];
	int is_anagram, i;

	/*Initilize the counts to zero */
	memset(count1, 0, sizeof(int) * NUM_CHARACTERS);
	memset(count2, 0, sizeof(int) * NUM_CHARACTERS);
	
	/*Compute the character counts for str1 and str2*/
	while (*str1) {
		count1[(int)*str1]++;
		str1++;
	}
	
	while (*str2) {
		count2[(int)*str2]++;
		str2++;
	}
	
	/*Compare the counts*/
	is_anagram = 1;
	for (i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			is_anagram = 0;
			break;
		}
	}
	return is_anagram;
}



Java


/*
str1, str2: the two strings which we want to compare
Return value: true if the two strings are anagrams, false otherwise
*/
public static boolean areAnagrams( char[] str1, char[] str2) 	{
	/*Initilize the counts to zero */
	int[] count1 = new int[NUM_CHARACTERS]; //NUM_CHARACTERS is 256
	int[] count2 = new int[NUM_CHARACTERS];

	/*Compute the character counts for str1 and str2*/
	for (char c: str1) 
		count1++;

	for (char c : str2) 
		count2++;

	/*Compare the counts*/
	boolean isAnagram = true;
	for (int i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			isAnagram = false;
			break;
		}
	}

	return isAnagram;
}



Python


#str1, str2: the two strings which we want to compare
#Return value: True if the two strings are anagrams, False otherwise
def are_anagrams(str1, str2) :	
	count1 = [0] * NUM_CHARACTERS #NUM_CHARACTERS is 256
	count2 = [0] * NUM_CHARACTERS

	#Compute the character counts for str1 and str2
	for  c in str1:
		count1[ord(c)] += 1
	

	for  c in str2:
		count2[ord(c)] += 1
	
	#Compare the counts
	is_anagram = True
	if (count1 != count2):
		is_anagram = False
		
	return is_anagram