x
BAN USERI read in a book that the effect of >> on a signed int is undefined. That is, different compilers generated different types of code. Thus, I can up with this code.
#include <limits.h>
#include <stdio.h>
int main()
{
/* find the most significant bit (MSB) pos */
int msb_pos = (sizeof(int) * CHAR_BIT) - 1;
/* mov number 1 to the MSB pos and then xor with -1 */
int result = (1 << msb_pos) ^ -1;
printf("Result = %d\n", result);
printf("Builtin = %d\n", INT_MAX);
return result;
}
/* Locates an index i such that A[i] = i
array - input sorted list
from - from index
to - to index
returns an i such that A[i] = i; otherwise -1.
*/
int bin_search_index_match(int* array, int from, int to)
{
/* if the first elt is bigger than its index then we stop searching
because our input list is sorted and increasing. No index can catch the content */
if(array[from] > from)
return -1;
int mid = from + (to - from)/2;
if(array[mid] == mid)
return mid;
if(array[mid] > mid)
return bin_search_index_match(array, from, mid-1);
else
return bin_search_index_match(array, mid+1, to);
}
/*
Sorts the given binary array from the index 'from' to the index 'to'.
*/
void sortBinaryArray(int* array, int from, int to)
{
int left = from;
int right = to;
while (left < right)
{
if(array[left] > array[right]) /* one before zero is not ok */
{
array[right--] = 1;
array[left++] = 0;
continue;
}
while(left < right && array[left] == 0) /* zero in the left is fine */
left++;
while(right > left && array[right] == 1) /* one in the right is fine */
right--;
}
}
/*
array - input array
start - starting index of array
end - ending index of array
subStart - starting index of the longest subsequence
subEnd - ending index of the longest subsequence
*/
void subseq(int* array, int start, int end, int* subStart, int *subEnd)
{
int bestStart = start; /* current longest sequence's start index */
int bestEnd = start; /* current longest sequence's end index */
*subStart = start;
*subEnd = start;
while(1) {
bestStart = start;
/* continue as long as the elements are non-decreasing */
while((start < end) && (array[start] <= array[start+1]))
{
start++;
}
bestEnd = start;
/* did we find a subsequence longer than the current one? */
if((bestEnd - bestStart) > (*subEnd - *subStart))
{
*subStart = bestStart;
*subEnd = bestEnd;
}
start++;
/* we are done if the current subsequence is longer than the remaining number of elements. */
if((*subEnd-*subStart) >= (end-start))
break;
}
}
Complexity is linear.
- x May 10, 2013int CountFreq (int *A, int value, int low, int high)
{
int mid;
if (high < low)
return 0;
mid = low + (high - low);
if (A[mid] > value)
return CountFreq (A, value, low, mid - 1);
else if (A[mid] < value)
return CountFreq (A, value, mid + 1, high);
else
return 1 + CountFreq (A, value, low, mid - 1) + CountFreq (A, value, mid + 1, high);
}
int main() {
int A[6] = { 1, 2, 3, 3, 3, 4};
int value = 3;
int count = 0;
printf("%d\n", CountFreq(A, value, 0, sizeof(A)/sizeof(int)-1));
return 0;
}
minor comment: main is not a good function name. I was using it for just running my test.
- x May 31, 2015