[array & String & Macro exercise]

Today I share with you some basic exercises that have been sorted out recently , I hope it helped you .

 

 

Catalog

1 Simulation Implementation atoi

2 Looking for a single dog

3 Exchange the odd and even bits of a binary bit with a macro

4 Implemented by macro simulation offsetof

 4 Integer de duplication in sequence

5 Ordered sequence merging

---

 

1 Simulation Implementation atoi

We know ：atoi Is to convert the number in the string into an integer number , However, the following situations need special consideration ：

1 Null pointer

2 An empty string

3 A non numeric character was encountered

4 Out of range

  So we might as well use an enumeration type state To determine whether the current input is legal , The sign's positive and negative can define a flag.

enum state
{
	VALID,
	UNVALID,
};
enum state s = VALID;
int MyAtoi(const char* ps)
{
	if (NULL == ps)
	{
		s = UNVALID;
	    return 0;
    }
	int flag = 1;
    if (*ps == '+')
	{
		ps++;
	}
	else if (*ps == '-')
	{
	     flag = -1;
         ps++;
    }
	while (isspace(*ps))
	{
		ps++;
	}
	long long n = 0;
	while (isdigit(*ps))
	{
		n = n * 10 + flag*(*ps - '0');
		if (n > INT_MAX || n < INT_MIN)
		{
			s = UNVALID;
		    return 0;
		}
		ps++;
	}
	if (*ps == '\0')
		return (int)n;
	else
	{
		s = UNVALID;
		return 0;
    }


}
int main()
{
	const char* pc = "- a123456";
	int ret = MyAtoi(pc);
	if (s == VALID)
    {
		printf("%d\n", ret);
	}
	else
		printf(" Format error , Unable to print \n");
	return 0;
}

---

 

2 Looking for a single dog

Subject requirements ： Only two elements in an integer array are single （ Only once ）, Other elements appear twice , Please find out these two single elements .

We know ： If there is only one single element , You only need to connect each element in the array with each other ^ Can solve the problem . So what about two single elements ？

I i You might as well assume an integer array {1,1,2,2,3,3,4,4,5,6}, If each element in the array ^ Equivalent to 5^6, And what you get is 3, The key to solve this problem is how to 5 and 6 Divided into different groups ？

We found that ： take 5^6 Result (3) Every bit of binary is &1( From right to left ), If &1 Result ==1, Just remember the first time ==1 The location of , Suppose the position is marked as pos, Then let each element in the array move to the right pos position , If ==1, It is divided into an array , Not for 1 It is divided into another array , This will be 5 and 6 Assigned to different groups .

 

// Find out which two elements in an array are single （ There are only two other repeating elements ）
void GudgSgle(int arr[], int len,int*p1,int*p2)
{
	int ret = 0;
	int i = 0;
	int pos = 0;
	for (i = 0; i < len; i++)
	{
		ret ^= arr[i];
	}
	for (i = 0; i < 32; i++)
	{
		if ((ret >> i & 1) == 1)
		{
			pos = i;
			break;
		}
	}
	for (i = 0; i <len; i++)
	{
		if ((arr[i] >> pos & 1) == 1)
			*p1 ^= arr[i];
		else
			*p2 ^= arr[i];
	}
}
int main()
{
	int arr[12] = { 1,2,3,4,5,6,1,2,3,4 };
	int len = sizeof(arr) / sizeof(int);
	int single1 = 0;
	int single2 = 0;
	GudgSgle(arr, len,&single1,&single2);
	printf("%d %d\n", single1, single2);
	return 0;
}

---

 

3 Exchange the odd and even bits of a binary bit with a macro

First of all to see ： How to exchange odd bits and even bits of a binary bit ？ If you can get all odd bits and all even bits , Then move all odd bits to the left by one bit , All even bits move one bit to the right , Then add it up to solve the problem . The key is how to get all odd digits and all even digits ： Given a binary number 1111 1111 1111 1111 1111 1111 1111 1111, If you want to get odd bits, put the binary number &0101 0101 0101 0101 0101 0101 0101 0101（0x55555555)

If you want to get even bits, put the binary number &1010 1010 1010 1010 1010 1010 1010 1010 (0xaaaaaaaa)

// Write a macro ： Exchange the odd and even bits of an integer 
#define SWAP(num) (((num&0x55555555)<<1)+((num&0xaaaaaaaa)>>1))
int main()
{
	int num = 10;
	printf("%d\n", SWAP(num));
	return 0;
}

  And what you get is 5 Meet the requirements .

---

4 Implemented by macro simulation offsetof

offsetof It is to calculate the offset of a variable in the structure relative to the first address . In order to simplify the calculation , We might as well 0 Strong conversion to a structure pointer , Then reference the variables in the structure through this pointer , Take out its address , The address is numerically equal to the offset of the structure variable .

// Write a macro , Realize it by yourself offsetof
struct state
{
	char a;
	char b;
	short c;
	int d;
};

#define OFFSETOF(stuname,memname) (int)&(((struct state*)0)->memname)
int main()
{
	printf("%d\n", OFFSETOF(struct state, a));
	printf("%d\n", OFFSETOF(struct state, b));
	printf("%d\n", OFFSETOF(struct state, c));
	printf("%d\n", OFFSETOF(struct state, d));
	return 0;
}

The result ：

  Here's what's interesting ： take 0 Strong conversion to a structure pointer is not really used 0 Space at address , Only the simulation realizes the calculation of offset , You can also turn other numbers here , Just subtract this number later .

The following expression is also correct ：

---

 

 4 Integer de duplication in sequence

Given an array of integers , Remove the repeated numbers ： for example {1,2,2,2,5,5,3,9}, After weight removal, it becomes {1,2,5,3,9},

The idea of solving the problem is ： Traverse every element in the array , Compare this element with all other numbers that follow , If equal , This element will be overwritten by the next element （ The elements following this element move forward one bit ）

#include<stdio.h>
int main()
{
    int n=0;
    scanf("%d",&n);
    int i=0;
    int arr[1000]={0};
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    int j=0;
    int k=0;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(arr[j]==arr[i])
            {
                for(k=j+1;k<n;k++)
                    arr[k-1]=arr[k];
                n--;
                j--;
            }
        }
    }
    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

 

One of the most error prone is when an element is overwritten j--, take {1,2,2,2,5,5,3,9} Come on , When taking the second element with the second 3 When comparing elements , The second element will be overwritten , The array becomes {1,2,2,5,5,3,9},j If you don't -- Will jump directly to the present No 3 Bit elements , Will make No 3 The bit element is compared with the following , It ignores the covering elements , Will go wrong .

---

5 Ordered sequence merging

Subject requirements ： Merge two integer arrays arranged in ascending order into one integer array arranged in ascending order .

Their thinking ： You can create an integer array , Compare the other two arrays one by one , Put the smaller value in the created array .

#include<stdio.h>
int main()
{
    int m=0;
    int n=0;
    int arr1[1000]={0};
    int arr2[1000]={0};
    int arr3[3000]={0};
    scanf("%d%d",&m,&n);
    int i=0;
    for(i=0;i<m;i++)
    {
        scanf("%d",&arr1[i]);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr2[i]);
    }
    i=0;
    int j=0;
    int k=0;
    while(i<m && j<n)
    {
        if(arr1[i]>arr2[j])
        {
            arr3[k++]=arr2[j];
            j++;
        }
        else
        {
            arr3[k++]=arr1[i];
            i++;
        }
    }
    if(i==m)
        for(;j<n;j++)
            arr3[k++]=arr2[j];
    else
        for(;i<m;i++)
            arr3[k++]=arr1[i];
    for(i=0;i<k;i++)
        printf("%d ",arr3[i]);
    return 0;
}

If one array is traversed but the other array is not traversed , Just put the element one that has not been traversed One is assigned to the created array .